АЛГОРИТМЫН ЦАГААН ТОЛГОЙ

Тоог 8 суурьтай тооллын системд шилжүүлэхэд урд болон хойноосоо ижил уншигдаж байвал түүнийг 8 суурьтай тооллын систем дэх палиндром тоо гэе. Тэгвэл өгөгдсөн t ширхэг бүхэл тоо бүрийн хамгийн ойр орших 8 суурьтай тооллын системд палиндром тоог олох програм бичнэ үү. Үр дүнгийн өгөгдлийг 10 суурьтай тооллын системээр файлд бичнэ. Уг тооноос их болон бага палиндром тоо ижил зайд байгаа бол ихийг нь үр дүн болгон авна. Оролтын өгөгдөл MAXLONGINT-ээс хэтрэхгүй.

Input

Оролтын файлын эхний мөрөнд тестийн тоо 2<=t<=10, дараагийн мөрөнд t ширхэг тоо сул зайгаар тусгаардагдан өгөгдөнө. 

Output

Оролтын i дүгээр өгөгдөлд харгалзах шийд i дүгээр мөрөнд байрлана. Гаралтын файлын нэг мөрөнд нэг тоо байна.

Example

Input:

2

12 254

Output:

9

251