Sachverhalt:
A.
Die Staatsanwaltschaft Zürich-Limmat warf X._ in der Anklage vom 23. September 2014 im Anklagesachverhalt 1 rechtswidrige Einreise und rechtswidrigen Aufenthalt i.S.v. Art. 115 Abs. 1 lit. a und lit. b des Bundesgesetzes über die Ausländerinnen und Ausländer (AuG; SR 142.20) sowie im Anklagesachverhalt 2 mehrfache rechtswidrige Einreise ins Ausland i.S.v. Art. 115 Abs. 2 AuG vor.
B.
Das Bezirksgericht Zürich trat am 19. Februar 2015 auf den Anklagesachverhalt 2 (rechtswidrige Einreise ins Ausland im Zusammenhang mit der Reise in die Niederlanden) nicht ein. Im Übrigen (Anklagesachverhalt 1 sowie Anklagesachverhalt 2 betreffend rechtswidrige Einreise ins Ausland im Zusammenhang mit der Reise nach Luxemburg) sprach es ihn frei. Es sprach ihm eine Genugtuung von Fr. 600.-- für drei Tage Untersuchungshaft vom 25. bis 28. Juni 2013 zu.
Das Obergericht des Kantons Zürich erkannte am 31. August 2015 auf Berufung der Staatsanwaltschaft X._ der Vergehen gegen das Ausländergesetz im Sinne von Art. 115 Abs. 1 lit. a sowie lit. b AuG schuldig (Dispositiv Ziff. 1) und stellte das Verfahren bezüglich Art. 115 Abs. 2 AuG betreffend den Anklagesachverhalt 2 ein ( Ziff. 2). Es verurteilte ihn zu einer Geldstrafe von 40 Tagessätzen zu Fr. 10.-- als Zusatzstrafe zum Strafbefehl der Staatsanwaltschaft Graubünden vom 12. April 2012, wovon 3 Tage durch erstandene Haft abgegolten sind ( Ziff. 3), schob den Vollzug der Geldstrafe auf und setzte eine Probezeit von 2 Jahren fest ( Ziff. 4). Die Kosten der Untersuchung sowie der beiden gerichtlichen Verfahren (exklusive Kosten der amtlichen Verteidigung) wurden ihm zu zwei Dritteln auferlegt und im verbleibenden Drittel auf die Gerichtskasse genommen ( Ziff. 8). Die Kosten der amtlichen Verteidigung für das gesamte Verfahren wurden einstweilen auf die Gerichtskasse genommen, unter Vorbehalt einer Rückforderung über zwei Drittel der Kosten der amtlichen Verteidigung gemäss <ref-law> ( Ziff. 9). Es wurde ihm für die erstandene Haft [ Ziff. 3] keine Genugtuung zugesprochen ( Ziff. 10).
C.
X._ beantragt mit Beschwerde in Strafsachen:
1. die Dispositiv-Ziffern 1, 3, 4, 8, 9 und 10 des obergerichtlichen Urteils aufzuheben,
2. ihn vom Vorwurf des vorsätzlichen Vergehens gegen Art. 115 Abs. 1 lit. a und b AuG (rechtswidrige Einreise und rechtswidriger Aufenthalt) freizusprechen,
3. ihm eine Genugtuung in der Höhe von Fr. 600.-- auszurichten,
4. die gesamten Untersuchungs- und gerichtlichen Verfahrenskosten aller Instanzen inklusive derjenigen der amtlichen Verteidigung auf die Staatskasse zu nehmen,
[5.] ihm die unentgeltliche Rechtspflege und Verbeiständung zu gewähren.

Erwägungen:
1.
Weil die Anforderungen des Anklageprinzips nicht erfüllt waren, stellte die Vorinstanz das Verfahren betreffend den Anklagesachverhalt 2 in Anwendung von <ref-law> ein.
2.
Im Anklagesachverhalt 1 wird dem Beschwerdeführer vorgeworfen, er sei am 7. Juli 2011 aus einem Nachbarland in Kenntnis der hiesigen Einreisevorschriften in die Schweiz eingereist, ohne über einen Reisepass und das erforderliche Visum zu verfügen. Nach der Abweisung seines Asylgesuchs am 5. August 2011 habe er sich bis zu seiner Ausreise im Oktober 2011 widerrechtlich in der Schweiz aufgehalten. Da er sich um den Stand seines am Tag der Einreise angestrengten Asylverfahrens nicht erkundigt habe, habe er Letzteres zumindest in Kauf genommen (Urteil S. 5).
2.1. Die Erstinstanz begründete den Freispruch damit: Es sei eingestanden und erstellt, dass der Beschwerdeführer am 7. Juli 2011 in die Schweiz einreiste. Hingegen sei seine Darstellung nicht zu widerlegen, er sei durch Grenzbeamte in Chiasso zur Stellung eines Asylgesuchs nach Altstätten gewiesen worden, was einer mündlichen Einreisebewilligung entspreche. Es könne ihm auch nicht rechtsgenügend nachgewiesen werden, dass er sich nach dem 15. Juli 2011, dem Datum des Verlassens des Empfangs- und Verfahrenszentrums (EVZ) Altstätten, noch in der Schweiz aufgehalten habe (Urteil S. 5 f.).
2.2. Die Vorinstanz schliesst sich dieser Beurteilung nicht an. Wie sie feststellt, sagte der Beschwerdeführer in der polizeilichen Befragung vom 26. Juni 2013, er habe bei seiner Einreise in die Schweiz ("gut möglich") am 7. Juli 2011 keine Reisepapiere besessen und sei an der Grenze nicht kontrolliert worden (Urteil S. 6, E. 1.5.1).
An der staatsanwaltschaftlichen Befragung erklärte der Beschwerdeführer, er habe bei seiner Einreise am 7. Juli 2011 von Italien her kommend direkt an der Grenze Asyl beantragt. Vorher habe er "ab 1987 oder 1988" in Italien gelebt, wobei er zwischenzeitlich nach Libyen zurückgekehrt sei. Den zusammenfassenden Vorhalt, er habe sich ab seiner Einreise am 7. Juli bis zum Oktober 2011 in der Schweiz aufgehalten und sei dann nach Holland ausgereist, beantwortete er mit: "Ja, ich bin dann nach Holland gegangen." An der Hauptverhandlung erklärte er, er sei ohne Pass und Visum in die Schweiz eingereist und habe in Chiasso ein Asylgesuch gestellt. "[D]ie Leute an der Grenze" hätten ihn nach Altstätten geschickt. An der Berufungsverhandlung erklärte er, in Chiasso habe er sich den Behörden gestellt, wo man ihm ein Ticket gegeben habe, um zur Asylempfangsstelle zu fahren. Wie lange er anschliessend geblieben sei, könne er nicht genau sagen. Es sei möglich, dass er im Oktober nach Holland gereist sei (Urteil S. 6 f.).
Die Vorinstanz stellt fest, die Aussagen erwiesen sich als äusserst unverlässlich, was auch die Verteidigung konstatiere. Praktisch durchwegs mache er Vergesslichkeit geltend und schildere einen schlechten generellen und auch psychischen Gesundheitszustand (Urteil S. 7 f.).
Hinsichtlich des Asylgesuchs sei er bei seiner ersten Angabe zu behaften, wonach er bei der Einreise nicht kontrolliert wurde. Seine späteren Aussagen widersprächen dieser Angabe diametral und wirkten nachgeschoben. Das sei als Schutzbehauptung und unglaubhaft zu taxieren. Wäre er bei der Einreise tatsächlich kontrolliert und von der Behörde weitergewiesen worden, hätte er keinen Grund gehabt, dies bei seiner ersten sowie eingangs der zweiten Befragung zu verschweigen und eine gegenteilige Version zu schildern (Urteil S. 8 f.).
Noch deutlicher gelte dies für seine Behauptung, er habe die Schweiz nicht erst im Oktober 2011 verlassen. Er habe bezüglich des abschlägigen Asylentscheids offensichtlich einiges verwechselt. Seine Aussage an der Hauptverhandlung sei das klare Ergebnis einer Suggestivfrage (Urteil S. 9). Eine Ausreise bereits nach wenigen Tagen oder Wochen habe er selber nie ins Feld geführt. Eine Ausreise am Tag des Stellens des Asylgesuchs sei abwegig (Urteil S. 10).
Somit bestünden keine Zweifel am Anklagesachverhalt. Entgegen der Erstinstanz habe der Beschwerdeführer nach dem Beweisresultat bei seiner Einreise keine mündliche Einreisebewilligung im Sinne von Art. 21 Asylgesetz (AsylG; SR 142.31) erhalten. Sein nachmaliger Status als Asylsuchender habe ihn nicht davon entbunden, sich an die konkreten Einreisebestimmungen zu halten (<ref-ruling> E. 2.3). Gemäss Art. 31 Abs. 1 des Abkommens über die Rechtsstellung der Flüchtlinge (SR 0.142.30) sei die illegale Einreise und der unrechtmässige Aufenthalt bei triftigen Gründen gerechtfertigt (<ref-ruling> E. 4.3). Der Beschwerdeführer sei weder direkt aus Libyen eingereist noch habe er für die Einreise triftige Gründe darlegen können. Er habe mehr als 30 Jahre in Italien unbehelligt gelebt und sei in dieser Zeit mehrmals nach Libyen gereist. Ein entsprechender Rechtfertigungsgrund liege nicht vor (Urteil S. 11).
2.3. Der Beschwerdeführer rügt eine Verletzung des Grundsatzes in dubio pro reo in seinen beiden Aspekten als Maximen der Beweislastverteilung und der Beweiswürdigung.
2.3.1. Dem Grundsatz in dubio pro reo als Beweiswürdigungsmaxime kommt keine über das Willkürverbot hinausgehende Bedeutung zu (<ref-ruling> E. 7; <ref-ruling> E. 2a; <ref-ruling> E. 2d S. 38). Als Beweislastmaxime bedeutet der Grundsatz, dass es Sache der Anklagebehörde ist, die Schuld des Angeklagten zu beweisen, und nicht dieser seine Unschuld nachweisen muss (BGE <ref-ruling> E. 2a).
Die freie Beweiswürdigung (<ref-law>) ist primäre Aufgabe der Sachgerichte (vgl. Art. 97 Abs. 1 und <ref-law>), weshalb das Bundesgericht nur bei Willkür eingreift.
Die Sachverhaltsfeststellung bzw. Beweiswürdigung erweist sich als willkürlich (<ref-law>), wenn das Gericht Sinn und Tragweite eines Beweismittels offensichtlich verkannt hat, wenn es ohne sachlichen Grund ein wichtiges und entscheidwesentliches Beweismittel unberücksichtigt gelassen oder wenn es auf der Grundlage der festgestellten Tatsachen unhaltbare Schlussfolgerungen gezogen hat. Dass die von Sachgerichten gezogenen Schlüsse nicht mit der Darstellung des Beschwerdeführers übereinstimmen, belegt keine Willkür (<ref-ruling> E. 2.3). Selbst wenn eine andere Lösung ebenfalls als vertretbar oder gar als zutreffender erscheinen mag, genügt das praxisgemäss nicht für die Annahme von Willkür (<ref-ruling> E. 2.2, 49 E. 3.4 sowie <ref-ruling> E. 6.1 betreffend Willkür in der Rechtsanwendung).
2.3.2. Für das Bundesgericht ist grundsätzlich der vorinstanzlich beweismässig festgestellte Sachverhalt massgebend (<ref-law>). Die vorinstanzliche Sachverhaltsfeststellung kann vor Bundesgericht nur gerügt werden, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht und wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>). Offensichtlich unrichtig ist die Sachverhaltsfeststellung, wenn sie willkürlich ist (<ref-ruling> E. 2.3).
Für die Anfechtung des Sachverhalts gilt das strenge Rügeprinzip (Art. 42 Abs. 2 i.V.m. Art. 97 Abs. 1 und Art. 106 Abs. 2 BGG). Das Bundesgericht prüft in diesem Fall nur klar anhand der angefochtenen Beweiswürdigung detailliert erhobene und aktenmässig belegte Rügen. Auf appellatorische Kritik tritt es nicht ein (<ref-ruling> E. 2.3; <ref-ruling> E. 1.4 und 6.2; Urteil 6B_841/2015 vom 10. November 2015 E. 2.2 mit Hinweisen).
2.4. Der Beschwerdeführer bringt vor, seine Aussagen hinterliessen einen durchgehend diffusen Eindruck und seien nicht nachvollziehbar. Dieses wirre Aussageverhalten lasse sich einerseits durch sein im November 2011 erlittenes Schädel-Hirntrauma und die Folgemedikation erklären und andererseits dadurch, dass er erstmals im Juni 2013 von der Polizei befragt worden sei (oben E. 2.2). Zu jener Zeit sei er bereits mehrere Male in verschiedene Länder ein- und ausgereist. Es sei daher "mehr als nachvollziehbar", dass er keine genauen Angaben mehr zur Ein- bzw. Ausreise geben konnte (Beschwerde S. 6).
Die rege Reisetätigkeit belegt einen durchaus intakten psycho-physischen Gesundheitszustand (andernfalls wäre sie ausgeschlossen gewesen) und bestätigt, dass die behauptete Traumatisierung und medikamentös induzierte Vergesslichkeit nicht ein Ausmass erreicht haben konnte, sodass der Beschwerdeführer den einfachen Sachverhalt der Art und Weise seiner erstmaligen Einreise in die Schweiz (anders als in seiner ersten polizeilichen Befragung) in der Folge nur noch "diffus", "wirr", höchst widersprüchlich und schliesslich mit einer gegenteiligen Version hätte angeben können.
Der Beschwerdeführer macht ferner geltend, seine Aussagen bei der polizeilichen Befragung und den späteren Einvernahmen seien nicht taktischer Natur gewesen (Beschwerde S. 6). Das mag für die polizeiliche Befragung zutreffen. Das vorinstanzliche Beweisergebnis, seine späteren Aussagen widersprächen der ersten Angabe diametral, wirkten nachgeschoben und seien als Schutzbehauptung und unglaubhaft zu taxieren, lässt sich aber nicht als unhaltbar qualifizieren.
2.5. Indem der Beschwerdeführer vorbringt, er sei an ein Asylzentrum verwiesen worden und habe damit eine mündliche Einreisebewilligung erhalten, widerspricht er der Beweiswürdigung und seiner ersten Aussage, ohne seine Behauptung durch irgend eine Aktenstelle, etwa auch durch einen Beleg aus den migrationsrechtlichen Abklärungen, zu belegen (im Asylverfahren hat der Asylsuchende gemäss <ref-law> an der Feststellung des Sachverhalts mitzuwirken). Damit wird keine Willkür aufgezeigt.
Über die vom Beschwerdeführer aufgeworfenen Fragen, u.a. wieso er unnötigerweise die lange Zugfahrt von fast fünf Stunden hätte auf sich nehmen sollen, wenn er sein Asylgesuch gleich an der Grenze hätte stellen können (Beschwerde S. 8), hat das Bundesgericht nicht zu mutmassen. Nach seiner Erstaussage reiste er in die Schweiz ein, ohne kontrolliert worden zu sein. Inwiefern diese Feststellung, angesichts seiner tatsächlichen Aussage, dass er bei der Einreise in die Schweiz "nicht kontrolliert worden sei" (anerkannt in Beschwerde S. 8), willkürlich sein sollte, ist nicht ersichtlich, und zwar um so weniger, als er auch nach seinen Vorbringen in der Folge ein "wirres Aussageverhalten" an den Tag legte.
Der Beschwerdeführer wendet ein, das Wort "Kontrolle" werde überdies mit dem arabischen Wort "Fahess" übersetzt, welchem auch die Bedeutung einer Leibesvisitation zukomme. Das schliesse jedoch in keiner Weise aus, dass er nicht von sich aus zu den Grenzbehörden gegangen sei und um Asyl ersucht habe (Beschwerde S. 9). Es finden sich indessen keine Indizien, dass der Beschwerdeführer von der Grenzbehörde aufgrund eines behaupteten Asylgesuchs ohne jede Vorkehr und ohne irgendeinen aktenkundigen Vermerk in die Schweiz (bzw. Altstätten) geschickt worden wäre. Das erscheint ausgesprochen zweifelhaft. Es kann bezüglich seiner Einreise weder von "klaren, konstanten und mehrfach wiederholten Aussagen" ausgegangen werden, noch schliesst die Vorinstanz "einzig und allein" aus einer Aussage auf ein verpöntes Verhalten (Beschwerde S. 11). Sie würdigt die Erstaussage im Gesamtzusammenhang seiner Angaben, der Indizien und Erfahrungssätze (vgl. dazu Urteil 6B_1145/2014 vom 26. November 2015 E. 1.1 zweiter Absatz).
Im Übrigen ist anzumerken: Ein Asylgesuch kann zwar auch mündlich bei der Grenzkontrolle an der Schweizer Grenze gestellt werden (vgl. Art. 18 und 19 AsylG). Behörden, bei welchen sich der Asylsuchende meldet, nehmen dessen Personalien auf, weisen ihn einem EVZ zu (<ref-law>), informieren dieses entsprechend und stellen ihm zu diesem Zweck einen Passierschein aus (CONSTANTIN HRUSCHKA, in: Marc Spescha et al. [Hrsg.], Kommentar Migrationsrecht, 4. Aufl. 2015, Rz. 1 zu <ref-law>). Nach der nachträglichen, nicht substanziierten Behauptung des Beschwerdeführers hätten ihn die Grenzschutzbeamten in Verletzung elementarer Amtspflichten ohne Registrierung und ohne jegliche weiteren Vorkehren einfach nach Altstätten geschickt. Das lässt sich nicht zu seinen Gunsten unterstellen.
2.6. Der Beschwerdeführer bringt vor, er sei am 15. Juli 2011 aus dem Empfangs- und Verfahrenszentrum (EVZ) Altstätten "verschwunden", weswegen sein Asylgesuch vom Bundesamt für Migration als gegenstandslos abgeschrieben wurde. Es könne den Akten jedoch nicht entnommen werden, wo er sich nach seinem Verschwinden aufgehalten habe. Es lasse sich somit nirgends ein Beweis dafür finden, dass er sich in der Schweiz aufgehalten habe (Beschwerde S. 12 f.). Er erwähnt neben weiteren Aussagen, er habe im Verfahren ausgeführt, er sei vielleicht 15 bis 20 Tage in der Schweiz geblieben und habe dann den Drang verspürt, die Schweiz zu verlassen. Auf die Frage, ob das im Oktober 2011 gewesen sei, habe er gesagt, das sei möglich. Er habe also gar nicht versucht, etwas zu bestreiten, woran er sich selber gar nicht mehr genau erinnern könne. Das sei ihm zugutezuhalten. Es ergebe sich ausserdem, dass sein Aufenthalt im Sommer 2011 nur von kurzer Dauer gewesen sein könne (Beschwerde S. 14).
Diese Einwände sind unbehelflich. Damit lässt sich nicht in dubio pro reo annehmen, der Beschwerdeführer habe sich nach seinem "Verschwinden" nicht in der Schweiz aufgehalten.
2.7. Die Beweiswürdigung erweist sich nicht als offensichtlich unrichtig (<ref-law>). Eine Verletzung des Grundsatzes in dubio pro reo ist zu verneinen, und zwar sowohl in seinem Gehalt als Beweiswürdigungsmaxime wie in jenem als "Beweislastregel" (BGE <ref-ruling> E. 2a). Letztere wird auch nicht dadurch verletzt, dass die Vorinstanz feststellt, der Beschwerdeführer habe eine Ausreise bereits nach wenigen Tagen oder Wochen selber nie ins Feld geführt (Beschwerde S. 15). Gegen den Grundsatz in dubio pro reo wird andererseits auch nicht dadurch verstossen, dass die Vorinstanz nicht eine sofortige Ausreise zugunsten des Beschwerdeführers unterstellt. Dafür besteht kein Indiz. Die Beschwerdeführung erweist sich als appellatorisch.
3.
Soweit sich der Beschwerdeführer gegen die rechtliche Würdigung im Sinne von Art. 115 Abs. 1 lit. a und lit. b AuG wendet, stützt er sich auf eine abweichende tatsächliche Version, ohne sich mit den rechtlichen Erwägungen des Urteils gemäss Art. 42 Abs. 2 i.V.m. <ref-law> auseinander zu setzen (vgl. Urteil 6B_423/2015 vom 27. November 2015 E. 2.2). Darauf ist nicht einzutreten.
4.
Der Antrag auf Genugtuung betrifft die drei Hafttage. Diese wurden auf die Strafe angerechnet (<ref-law>; oben Bst. B). Es besteht kein Anspruch auf Genugtuung (<ref-ruling> E. 3.3).
5.
Auf die übrigen, offensichtlich hinsichtlich einer Gutheissung gestellten und nicht weiter begründeten Rechtsbegehren ist nicht einzutreten.
6.
Die Beschwerde ist abzuweisen, soweit darauf eingetreten werden kann. Das Gesuch um unentgeltliche Rechtspflege (und Verbeiständung) musste trotz der erstinstanzlichen Entscheidung angesichts der vorinstanzlichen Beurteilung und der unbehelflichen Einwände als von vornherein aussichtslos erscheinen (<ref-law>; <ref-law>). Das Gesuch ist abzuweisen. Die Gerichtskosten sind dem Beschwerdeführer aufzuerlegen und angesichts seiner Mittellosigkeit praxisgemäss herabzusetzen (Art. 66 Abs. 1 i.V.m. Art. <ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.
Das Gesuch um unentgeltliche Rechtspflege wird abgewiesen.
3.
Die Gerichtskosten von Fr. 1'600.-- werden dem Beschwerdeführer auferlegt.
4.
Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zürich, I. Strafkammer, schriftlich mitgeteilt.
Lausanne, 8. Februar 2016
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Denys
Der Gerichtsschreiber: Briw