Background背景

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

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

请你编程帮助小丽找符合条件的半个回文数。

Input输入

第一行是一个整数 n（$5 \le n \le 100$）；

第二行是 n 个整数（这些整数都是 [0,$10^8$] 之间的整数）；

Output输出

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

Samples样例

5
121 417 27 100 21

417
27
21

Limitation限制

1s, 1024KiB for each test case.