Faits:
A.
Par jugement du 1 er mars 2013, le Tribunal correctionnel genevois a acquitté A._ du chef d'accusation de tentative d'instigation à assassinat, l'a condamné pour tentative d'instigation à lésions corporelles graves et infractions à la LEtr à une peine privative de liberté de 30 mois, sous déduction de 337 jours de détention subie avant jugement, dont 10 mois fermes et le solde avec sursis pendant 4 ans et rejeté les conclusions civiles de la partie plaignante. Il a en outre alloué à A._ 15'000 fr. à titre de réparation morale, 30'000 fr. pour ses frais de défense, rejeté ses conclusions en réparation du dommage économique, ordonné la restitution des biens et valeurs séquestrés, sous déduction des frais de procédure mis à sa charge par 17'125 francs.
B.
Par arrêt du 24 septembre 2013, la Chambre pénale d'appel et de révision de la Cour de justice genevoise a rejeté les appels formés par le Ministère public et la partie plaignante et admis celui de A._. Elle a ainsi acquitté celui-ci des chefs d'accusation de tentative d'instigation à assassinat et de tentative d'instigation à lésions corporelles graves, l'a condamné pour infractions à la LEtr à une peine pécuniaire de 90 jours-amende à 50 fr., sous déduction de 90 jours de détention avant jugement, avec sursis pendant 3 ans. Elle a en outre alloué à A._ 100'000 fr. pour ses frais de défense, 55'000 fr. pour la perte de gain et 40'000 fr. à titre d'indemnité pour le tort moral et mis une part de 10% des frais de première instance, soit 1712 fr., à sa charge.
C.
A._ forme un recours en matière pénale au Tribunal fédéral contre cet arrêt. Il conclut, avec suite de frais et dépens, principalement à sa réforme en ce sens que l'Etat de Genève est condamné à lui payer 209'250 fr., TVA comprise, à titre d'indemnité pour les dépenses occasionnées par l'exercice raisonnable de ses droits de procédure jusqu'à l'arrêt rendu par la Cour de justice et 60'000 fr. pour la perte économique subie au titre de sa participation obligatoire à la procédure. Subsidiairement, il conclut à l'annulation de l'arrêt attaqué, au constat qu'il a droit à une indemnité équitable pour le dommage économique et au renvoi de la cause à l'autorité inférieure pour nouvelle décision au sens des considérants. Il requiert par ailleurs l'assistance judiciaire.
Invités à déposer des observations sur le recours, la Cour cantonale y a renoncé et le Ministère public a conclu à son rejet, tous deux se référant aux considérants de l'arrêt attaqué.
Considérant en droit:
1.
Les prétentions en indemnisation fondées sur l'art. 429 CPP peuvent faire l'objet d'un recours en matière pénale (ATF 139 IV 206 consid. 1 p. 208).
2.
2.1. Le Tribunal fédéral conduit son raisonnement sur la base des faits établis par la juridiction précédente (art. 105 al. 1 LTF). Il ne peut s'en écarter que si ces faits ont été établis de façon manifestement inexacte - à savoir arbitraire (ATF 137 II 353 consid. 5.1 p. 356). Le grief d'arbitraire doit être invoqué et motivé de manière précise (art. 106 al. 2 LTF). Le recourant doit exposer, de manière détaillée et pièces à l'appui, que les faits retenus l'ont été d'une manière absolument inadmissible, et non seulement discutable ou critiquable. Il ne saurait se borner à plaider à nouveau sa cause, contester les faits retenus ou rediscuter la manière dont ils ont été établis comme s'il s'adressait à une juridiction d'appel (ATF 133 IV 286). Le Tribunal fédéral n'entre pas en matière sur les critiques de nature appellatoire (ATF 137 II 353 consid. 5.1 p. 356 ; 133 III 393 consid. 6 p. 397).
2.2. Le recourant débute ses écritures par une présentation personnelle des faits. Dans la mesure où il s'écarte des faits retenus par la cour cantonale sans démontrer que ceux-ci auraient été établis de manière arbitraire, son exposé est appellatoire, partant irrecevable.
3.
Le recourant fait grief à la cour cantonale d'avoir violé les art. 429 al. 1 let. b CPP et 42 CO.
3.1. Aux termes de l'art. 429 al. 1 let. b CPP, si le prévenu est acquitté totalement ou en partie ou s'il bénéficie d'une ordonnance de classement, il a droit à une indemnité pour le dommage économique subi au titre de sa participation obligatoire à la procédure pénale.
L'évaluation du dommage économique se fait en application des règles générales en matière de responsabilité civile ( WEHRENBERG/BERNHARD, in Basler Kommentar, Schweizerische Strafprozessordnung, 2011, n o 25 ad art. 429 CPP; MIZEL/RÉTORNAZ, in Commentaire romand, Code de procédure pénale suisse, 2011 n o 41 ad art. 429 CPP; Jo Pitteloud, Code de procédure pénale suisse, Commentaire à l'usage des praticiens, 2012, no 1342 p. 885; Jeanneret/Kuhn, Précis de procédure pénale, 2013, no 5064).
Conformément aux principes généraux, le dommage correspond à la diminution involontaire de la fortune nette. Il peut consister dans une réduction de l'actif, en une augmentation du passif ou dans un gain manqué; il équivaut à la différence entre le montant actuel du patrimoine et le montant que celui-ci aurait atteint si l'événement dommageable ne s'était pas produit (ATF 139 V 176 consid. 8.1.1 p. 187 s.; 133 III 462 consid. 4.4.2 p. 470 et les références citées). Le responsable n'est tenu de réparer que le dommage qui se trouve dans un rapport de causalité adéquate avec l'acte qui fonde sa responsabilité (cf. 133 III 462 consid. 4.4.2 p. 470). Il appartient au lésé de prouver non seulement l'existence et l'étendue du dommage, mais aussi le lien de causalité entre celui-ci et l'événement à la base de son action.
A teneur de l'art. 42 al. 2 CO, lorsque le montant exact du dommage ne peut pas être établi, le juge le détermine équitablement en considération du cours ordinaire des choses et des mesures prises par la partie lésée. Cette disposition édicte une règle de preuve de droit fédéral dont le but est de faciliter au lésé l'établissement du dommage. Elle s'applique aussi bien à la preuve de l'existence du dommage qu'à celle de son étendue. L'art. 42 al. 2 CO allège le fardeau de la preuve, mais ne dispense pas le lésé de fournir au juge, dans la mesure du possible, tous les éléments de fait constituant des indices de l'existence du préjudice et permettant l'évaluation ex aequo et bono du montant du dommage. Les circonstances alléguées par le lésé doivent faire apparaître un dommage comme pratiquement certain; une simple possibilité ne suffit pas pour allouer des dommages-intérêts. L'exception de l'art. 42 al. 2 CO à la règle du fardeau de la preuve doit être appliquée de manière restrictive (ATF 133 III 462 consid. 4.4.2 p. 471 et les références citées).
3.2. Dire s'il y a eu dommage et quelle en est la quotité est une question de fait qui lie en principe le Tribunal fédéral (art. 105 al. 1 et 2 LTF). C'est en revanche une question de droit (art. 106 al. 1 LTF) de dire si la notion juridique du dommage a été méconnue et de déterminer si l'autorité cantonale s'est fondée sur des principes de calcul admissibles pour le fixer (ATF 139 V 176 consid. 8.1.3 p. 188). Lorsque les conditions d'application de l'art. 42 al. 2 CO sont réunies, l'estimation du dommage repose sur le pouvoir d'apprécier les faits; elle relève donc de la constatation des faits (ATF 126 III 388 consid. 8a p. 389). Or, saisi d'un recours en matière pénale, le Tribunal fédéral ne réexamine l'établissement des faits - sous réserve de l'allégation d'une violation du droit au sens de l'art. 95 LTF - que lorsqu'il est entaché d'inexactitude manifeste (art. 97 al. 1 LTF), à savoir d'arbitraire (ATF 137 IV 1 consid. 4.2.3 p. 5).
3.3. En substance, la cour cantonale a relevé que le recourant réclamait un montant de 60'000 fr. pour paiement d'une partie des loyers de son magasin durant son incarcération, de salaires payés aux employés et pour la perte de clientèle. Il ressortait toutefois de ses déclarations que le magasin n'avait été fermé en raison de sa détention que durant les mois de mars, avril, mai, septembre et octobre 2012, d'autres personnes l'ayant exploité par ailleurs. Les cinq mois de fermeture allégués ne reposaient que sur les déclarations du recourant qui ne trouvaient aucune confirmation dans les pièces produites et les témoignages figurant à la procédure, la comptabilité pour l'exercice 2012 n'étant pas à la disposition de la cour cantonale. La comptabilité de l'exercice 2011 n'était d'aucun secours, la comptable ayant déclaré l'avoir établie sans disposer des pièces comptables, saisies par la police. Les déclarations de celle-ci et du recourant relatives à la période de fermeture du magasin ne concordaient pas, la comptable ayant parlé d'une fermeture complète durant la détention du recourant. Au vu de ces éléments, le recourant, qui avait le fardeau de la preuve, n'avait pas établi les faits de sorte qu'il devait être débouté de ses conclusions sur ce point.
3.4. Le recourant se contente d'affirmer qu'il aurait établi son dommage, dans toute la mesure du possible au vu des circonstances, se référant pour cela à ses propres déclarations et à celles de sa comptable. Il soutient également que le contenu de son magasin aurait été détruit en mars 2012 et que la surmédiatisation de l'affaire lui aurait causé une perte de clientèle. Ce faisant, il ne fait qu'opposer sa propre appréciation des faits à celle de la cour cantonale, sans démontrer en quoi celle-ci serait arbitraire. Purement appellatoire, son grief est irrecevable. Il se plaint en outre du fait que la cour cantonale n'a pas fait application de l'art. 42 al. 2 CO. Cette disposition ne dispensait toutefois pas le recourant de fournir au juge, dans la mesure du possible, tous les éléments de fait constituant des indices de l'existence du préjudice et permettant l'évaluation ex aequo et bono du montant du dommage. Or, en l'espèce, la cour cantonale a retenu, sans que le recourant en démontre l'arbitraire, qu'il n'existait pas suffisamment d'indices pour établir le dommage. Insuffisamment motivé au regard des exigences accrues de l'art. 106 al. 2 LTF, sa critique est irrecevable. En l'absence de dommage établi, c'est à bon droit que la cour cantonale a refusé d'allouer au recourant une indemnité pour le dommage économique fondé sur l'art. 429 al. 1 let. b CPP.
4.
Le recourant se plaint de ce que la cour cantonale aurait violé l'art. 429 al. 1 let. a CPP en réduisant sa prétention en indemnisation pour ses frais de défense de plus de la moitié.
4.1. Aux termes de l'art. 429 al. 1 let. a CPP, le prévenu acquitté totalement ou en partie ou au bénéfice d'un classement a droit à une indemnité pour les dépenses occasionnées par l'exercice raisonnable de ses droits de procédure. L'indemnité concerne les dépenses du prévenu pour un avocat de choix (ATF 138 IV 205 consid. 1 p. 206). Elle couvre en particulier les honoraires d'avocat, à condition que le recours à celui-ci procède d'un exercice raisonnable des droits de procédure. Selon le message du Conseil fédéral, l'Etat ne prend en charge les frais de défense que si l'assistance d'un avocat était nécessaire compte tenu de la complexité de l'affaire en fait ou en droit et que le volume de travail et donc les honoraires étaient ainsi justifiés (Message du 21 décembre 2005 relatif à l'unification du droit de la procédure pénale, FF 2006 1313 ch. 2.10.3.1).
4.2. Lorsque le juge est amené à fixer l'indemnité pour frais de défense selon l'art. 429 al. 1 let. a CPP alors qu'une liste des opérations de l'avocat a été déposée, la garantie du droit d'être entendu implique qu'il doit, s'il entend s'en écarter, au moins brièvement indiquer les raisons pour lesquelles il tient certaines prétentions pour injustifiées, afin que son destinataire puisse attaquer la décision en connaissance de cause (arrêt 6B_875/2013 du 7 avril 2014 consid. 5).
4.3. En substance, la cour cantonale a retenu que, même si la cause n'était pas d'une complexité particulière, l'assistance d'un avocat était nécessaire, compte tenu de la nature des infractions reprochées et de la mise en détention. Elle a indiqué que la note d'honoraires principale, s'élevant à près de 180'000 fr., ne permettait pas de savoir quelles prestations avaient été effectuées par un associé ou par un stagiaire. Le temps consacré aux prestations fournies n'était pas indiqué pour chacune d'elles mais de manière globale, ce qui empêchait toute évaluation précise. La cour cantonale ne distinguait pas la nécessité des nombreuses heures de recherches juridiques facturées, ainsi que des entretiens entre associé et stagiaire, qui relevaient de l'organisation interne de l'étude. Elle a retenu un tarif horaire de 400 fr. pour un associé et 100 fr. pour un stagiaire. Au vu de ces éléments, elle a fixé à 100'000 fr. le montant de l'indemnité relative aux frais de défense.
4.4. La motivation cantonale ne permet pas de déterminer quelles prestations, hormis les heures de recherches juridiques et les entretiens entre associé et stagiaire, elle a considéré comme des prestations inutiles. Elle n'a en outre pas indiqué le temps qu'elle estimait comme utilement consacré à l'exécution du mandat, ni celui qu'elle estimait consacré à des démarches superflues. Le fait que les notes d'honoraires produites par le recourant n'indiquent pas en détail le temps consacré à chaque opération, mais uniquement une liste par jour des opérations et du temps global y afférent, n'empêchait pas la cour cantonale de procéder à une appréciation du temps qu'elle estimait comme utilement consacré à chaque opération. Si toutefois, elle considérait n'être pas suffisamment renseignée, elle devait, en application de l'art. 429 al. 2 CPP, enjoindre le recourant à préciser ses prétentions, en particulier à fournir des notes d'honoraires plus détaillées. Il en va de même s'agissant de la séparation des heures effectuées par un associé et celles effectuées par un stagiaire. La motivation cantonale ne permet ainsi pas de vérifier la bonne application du droit fédéral.
4.5. Le recourant conteste également la fixation du tarif horaire à 400 fr. pour l'associé et 100 fr. pour le stagiaire.
Selon la jurisprudence, l'indemnité visée par l'art. 429 al. 1 let. a CPP doit correspondre au tarif usuel du barreau applicable dans le canton où la procédure se déroule, à moins que le canton n'ait fixé un tarif réglementaire (cf. arrêt 6B_392/2013 du 4 novembre 2013 consid. 2.3).
Le canton de Genève n'a pas fixé de tarif. Dès lors, il y a lieu de se référer au tarif usuel du canton. Déterminer le taux horaire usuel est une question de fait que le Tribunal fédéral ne revoit que sous l'angle de l'arbitraire. A cet égard, le recourant soutient que le tarif horaire usuel pour un avocat associé se situe entre 400 et 450 francs. Il ne démontre pas en quoi il serait arbitraire de retenir un tarif horaire de 400 fr., comme l'a fait la cour cantonale, qui se situe dans la fourchette qu'il cite lui-même. Son grief à cet égard est irrecevable. Quant au tarif horaire de l'avocat stagiaire, le recourant soutient, se référant à la pratique de la Commission de taxation des honoraires d'avocat du canton de Genève, que la rémunération horaire de l'avocat stagiaire se situerait entre 180 et 200 fr. (cf. notamment BOHNET/MARTENET, Droit de la profession d'avocat, 2009, n o 2972 p. 1174). La cour cantonale n'expose pas pour quel motif elle a retenu un tarif horaire de 100 francs. Le recours doit être admis sur ce point. Dans le cadre du renvoi, elle devra établir la pratique usuelle du canton et se fonder sur ce tarif horaire pour rémunérer les heures utilement effectuées par un stagiaire.
5.
Au vu de ce qui précède, le recours doit être partiellement admis, la cause renvoyée à la cour cantonale pour nouvelle décision sur l'indemnité fondée sur l'art. 429 al. 1 let. a CPP. Pour le surplus, le recours est rejeté dans la mesure où il est recevable.
Le recourant a requis l'assistance judiciaire. Cette requête est sans objet dans la mesure où il obtient gain de cause et peut, à ce titre, prétendre à des dépens réduits de la part du canton (art. 64 al. 2 et 68 al. 1 LTF). Le recours était, pour le surplus, dénué de chances de succès, si bien que l'assistance judiciaire doit être refusée dans cette mesure (art. 64 al. 1 LTF). Une partie des frais sera ainsi supportée par le recourant (art. 66 al. 1 LTF), dont le montant sera toutefois fixé en tenant compte de sa situation financière.
Par ces motifs, le Tribunal fédéral prononce:
1.
Le recours est partiellement admis, l'arrêt attaqué annulé et la cause renvoyée à l'autorité cantonale pour nouvelle décision. Pour le surplus, le recours est rejeté, dans la mesure où il est recevable.
2.
Les frais judiciaires, arrêtés à 800 fr., sont mis à la charge du recourant.
3.
La demande d'assistance judiciaire est rejetée dans la mesure où elle n'est pas sans objet.
4.
Une indemnité de 1500 fr., à verser au conseil du recourant à titre de dépens, est mise à la charge du canton de Genève.
5.
Le présent arrêt est communiqué aux parties et à la Chambre pénale d'appel et de révision de la Cour de justice du canton de Genève.
Lausanne, le 10 juin 2014
Au nom de la Cour de droit pénal
du Tribunal fédéral suisse
Le Président: Mathys
La Greffière: Livet