Într­-un cămin din Cluj, în camera 616, stau 3 băieţi. Unul dintre ei, a observat că numărul camerei este un număr palindrom şi aşa au început să­şi pună unul altuia întrebări de genul:
“Care este al K­-lea număr palindrom?”
După o perioadă în care cei 3 şi-au tot pus astfel de întrebări, au ajuns la valori ale lui K din ce în ce mai mari şi le ia din ce în ce mai mult timp să răspundă, aşa că cei 3 băieţi au nevoie de ajutorul vostru.

Cerinţă

Răspunde-ţi la T întrebări pentru băieţi.

Date de intrare

Fişierul de intrare camera616.in conţine pe prima linie numărul de teste T. Pe fiecare dintre următoarele T linii se află câte o valoare K la care trebuie să răspundeţi.

Date de ieşire

Fişierul de ieşire camera616.out conţine răspunsul la cele T întrebări, câte unul pe linie, în ordinea dată.

Restricţii

• 1 <= T <= 8
• 1 <= K < 10¹⁰⁰⁰
• Primul număr palindrom este zero.
• Pentru 40% din teste K < 10⁹
• Pentru alte 30% din teste K < 10⁶⁴

Exemplu

camera616.in	camera616.out
4 1 3 13 616	0 2 33 51615

stud. Cosmin-Mihai Tutunaru

Universitatea Babeş-Bolyai

cosmin@tutunaru.ro