U126487 二进制

### 前置知识： - **二进制**：我们常说的1、2、3、4、5、6、7、8、9、10......是十进制是数字，即满十进一。而在计算机中往往运用的是二进制数字，即满二进一，如3在二进制中表示为11，5在二进制中表示位101。“int”是32位的整数，即存长度为32的一个整数。3在int中会被储存为000.....011（11前面还有30个0）。 - **异或(^)**：异或是编程中常用的一种运算符号，a^b的结果表明了a和b在二进制下每一个对应位置的数字是否相同，相同为0，不同为1。例如5^3=6，因为5是101，3是011（当然，如果在int的32位下他们前面都还有很多个0），101和011中左边第一位和第二位不同，所以答案是110，即十进制下的数字6。

给你一个十进制下的数字 _m_ ，那么一定存在至少一对十进制的32位整数下的数字 _x_ 和 _y_ 使得 _x^y=m_ 成立。你需要找出在 _x_ 与 _y_ 的和最大的情况下，在十进制下有多少组32位非负整数 _x_ 和 _y_ 使 _x^y=m_ 成立。 **简单地说，在使 _x、y_ 的和最大的情况下的和你能找到多少组 _x_ 和 _y_ 使 _x^y=m_ 成立。** **请注意：x=1、y=2和x=2、y=1视为两对不同的解**

第一行输入一个整数 _t_ ,表示共有 _t_ 组测试 ( _1≤t≤100000_ )。 以下 _t_ 行，每行一个数字 _m_ ( _0≤m≤1000000000_ )。

共 _t_ 行，每行打印一个十进制整数表示你的答案。

1表示有一组输入。 当 _m_ =2时，使 _x^y=m_ 成立的 _x、y_ 最大和为 _8589934586_ 。在最大和的条件下共有两组 _x、y_ 使得 _x^y=m_ 成立。 第一组：_x=4294967295，y=4294967291；_ 第二组：_x=4294967291，y=4294967295。_