小q最近迷上了各种好玩的数列，这天，他发现了一个有趣的数列，其递推公式如下： f[0]=0 f[1]=1; f[i]=f[i2]+f[i%2];(i=2) 现在，他想考考你，问：给你一个n，代表数列的第n项，你能不能马上说出f[n]的值是多少，以及f[n]所代表的值第一次出现在数列的哪一项中？（这里的意思是：可以发现这个数列里某几项的值是可能相等的，则存在这样一个关系f[n'] = f[n] = f[x2]+f[x%2] = f[x]...（n'

输入描述:

输入第一行一个t随后t行，每行一个数n，代表你需要求数列的第n项，和相应的n'(t4*10^5)

输出描述:

输出每行两个正整数f[n]和n'，以空格分隔