Faits : A. Par acte d'accusation du 5 septembre 2014, X._ a été renvoyé devant le Tribunal de police de l'arrondissement de l'Est vaudois pour abus de confiance, escroquerie et tentative d'escroquerie au préjudice de A._ (ci-après : A._) dans huit cas différents. Par jugement du 27 octobre 2015, ce tribunal a libéré X._ de toutes les préventions dont il était l'objet, a rejeté les conclusions civiles de A._, a ordonné la levée du séquestre imposé sur les comptes de X._, lui a alloué un montant de 26'400 francs à titre d'indemnités au sens de l'art. 429 CPP et a laissé les frais à la charge de l'Etat. B. Par jugement du 8 mars 2016, la Cour d'appel pénale du Tribunal cantonal vaudois a libéré X._ de la prévention d'escroquerie dans tous les cas et l'a condamné, pour abus de confiance dans un des cas, à une peine pécuniaire de 90 jours-amende à 70 fr. le jour, avec sursis pendant 2 ans. Elle a fait partiellement droit aux conclusions civiles de A._ à concurrence de 12'850 fr., a levé le séquestre ordonné sur le compte dépôt-titres no..., dont X._ est titulaire auprès de la banque B._, à concurrence de 12'850 fr. en faveur de A._ et dit, pour le surplus, que ce compte était à la libre disposition de X._. Enfin, elle a mis une partie des frais de procédure de première instance à la charge de X._, le solde étant laissé à la charge de l'Etat. Une indemnité de 19'800 fr. a été allouée à l'intéressé au sens de l'art. 429 CPP à charge de l'Etat. Pour la procédure de seconde instance, la cour cantonale a mis trois quarts des frais d'appel à la charge de A._ et un quart à la charge de X._. Elle a accordé à ce dernier une indemnité pour ses dépenses obligatoires occasionnées par la procédure d'appel à la charge de A._. Enfin, elle a compensé les indemnités dues à X._ par l'Etat avec les frais mis à sa charge. Ce jugement repose, en substance, sur l'état de fait suivant. X._ est arrivé en Suisse en 1995. Il a dispensé des cours de business et management. Il a créé la société C._ (ci-après : C._) à U._, dont il est l'unique associé gérant. Dès janvier 2004, il a travaillé pour le compte de A._ jusqu'au 9 août 2010, date à laquelle il a démissionné. Selon le contrat de travail liant les parties, X._ était rémunéré, d'une part, en fonction du nombre d'élèves inscrits à l'école et, d'autre part, par une commission de 10% en faveur de C._ sur les revenus d'écolages résultant des activités de promotion. De plus, l'employeur prenait à sa charge tous les frais engendrés par l'activité de promotion. La cour cantonale a retenu que A._ avait admis, ou à tout le moins toléré, que X._ perçoive en cash l'écolage de certains étudiants. Dans la mesure où le salaire dû était régulièrement payé avec retard, A._ avait admis une compensation entre ces montants et ceux dus à titre de salaire ou de remboursement de frais. Le 7 octobre 2009, D._ a versé un montant de 30'000 fr. sur le compte de la société C._ pour les frais d'écolage de E._. De ce montant, C._ a reversé une somme de 17'150 fr. à A._ le 12 octobre 2009 et a conservé le solde. Concernant F._, la cour cantonale a constaté que X._ avait admis avoir reçu l'écolage en question et avoir procédé à une compensation avec ce qui lui était dû. A._ ayant accepté l'encaissement d'écolages par X._, les explications peu claires de l'administrateur de l'école ne permettaient pas de mettre en doute une compensation possible. Partant, la cour cantonale n'a retenu aucune infraction à la charge de X._. Quant au décompte de frais de promotion au Brésil, la cour cantonale a retenu que ce document contenait un montant de 4800 euros, dont X._ avait dit qu'il représentait la somme que les autorités locales auraient prélevée à son arrivée sur territoire brésilien parce qu'il était dépourvu du visa nécessaire. Aucune explication n'avait été demandée à ce sujet à X._ avant sa démission. La cour cantonale a exposé ne pas voir quelle infraction celui-ci aurait commise dans de telles circonstances. C. X._ interjette un recours en matière pénale au Tribunal fédéral contre le jugement sur appel du 8 mars 2016 (dossier 6B_613/2016). Il conclut, avec suite de frais et dépens, à la réforme de cette décision en ce sens qu'il soit acquitté de toutes les préventions retenues contre lui, que les conclusions civiles de A._ soient rejetées, le séquestre de son dépôt-titres levé et qu'une indemnité au sens de l'art. 429 CPP lui soit allouée. Il requiert, par ailleurs, que l'effet suspensif soit accordé à son recours. A._ interjette un recours en matière pénale au Tribunal fédéral contre le même jugement (dossier 6B_627/2016). Elle conclut, avec suite de frais et dépens, principalement, à la réforme de cette décision dans le sens de la condamnation de X._ pour abus de confiance à une peine pécuniaire avec sursis, à l'allocation de ses conclusions civiles par 27'850 fr., à la levée du séquestre ordonné sur le compte dépôt-titres à concurrence de la même somme, à la mise à charge de X._ d'une partie des frais de première instance, au partage des frais d'appel entre les parties, à l'octroi à X._ d'une juste indemnité pour ses dépenses obligatoires occasionnées par la procédure d'appel ainsi que d'une indemnité au sens de l'art. 429 CPP à la charge de l'Etat. A titre subsidiaire, A._ conclut à l'annulation du jugement entrepris et au renvoi de la cause à la cour cantonale pour nouvelle décision au sens des considérants.