学密码学真的得学程序

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

话说,上次ZYJ同学最终在众位玛丽亚的帮助下搞定了那个神奇的字符串,然后神奇的事情发生了,字符串下面竟然有一个通道,ZYJ满怀激动的走下了通道。然而,不得不说,ZYJ同学是悲剧的,为什么呢,因为他走进了一个进制迷宫(谁让他乱闯的来着。。。。。),进制迷宫里有好多好多密码门。他很沮丧,因为他无法破解密码门的密码。这个时候WL看不下去了,于是降下神通,告诉ZYJ,每个密码门上都有一个数字a,那代表这个密码门是a进制的。密码门的密码即为所有小于等于300(这个300是十进制数)的正整数的平方在a进制下是回文串的所有数的和。密码门的密码是a进制的。用A表示10,B表示11,C表示13。。。。。。。

ZYJ竟然没听懂是什么意思,好吧,举个例子来说,如果a为2,那么所有小于等于300的正整数中只有1和3的平方(分别为1和9)在2进制中为回文串(1的二进制为1,是回文串,9的二进制是1001,也是回文串),所以这个密码门的密码是100(1+3=4,4在2进制下是100);

Input

 

第一行输入一个n代表有n扇门。

接下来的n行,每一行都有一个数字a(1<a<20),代表这扇门为a进制。

Output

 

输入每扇门的密码,每扇门的密码占一行。

Sample Input

2
10
2

Sample Output

1076
100

Hint

 

Source

zp