题目描述

炼石熊在编程中学到了回文数的概念，如果一个数正过来读和反过来读是同一个数，那么这个数就是回文数。比如：2、5、8、66、121、686、12321都是回文数。炼石熊发现这样的数不算多。

于是炼石熊有个想法：如果这个数不是回文数，但这个数在2进制或者16进制下是回文数，就算这个整数是半个回文数。比如417并不是回文，但417对应的16进制数是1A1是回文数，因此417算半个回文数。

请你编程帮助炼石熊找符合条件的半个回文数。

输入格式

第一行是一个整数n（10 ≤ n ≤ 100） 第二行是n个整数（这些整数都在long long范围内）

输出格式

所有符合条件的半个回文数，每行一个。

样例

输入

5
121 417 27 100 21

输出

417
27
21