C. Confusion
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Professor Claudio teaches programming at your university.

Today's lecture topic is attention. Clearly, attention is very important in programming: if you put just one or two extra characters into your program, it might crash!

However, for you, a grandmaster on Coffeeforces, the whole thing is absolutely boring. Sitting, doing nothing, and listening to things you already know certainly wasn't in your plans. It would definitely be better to solve another contest with your team to prepare for the regional competition instead... Other students, despite not being grandmasters, seem to agree with you.

When Claudio opened another slide of his presentation, it was dedicated to the importance of not confusing C++ language operators, referring in particular to the following common incorrect representation of the number $$$a^{b}$$$:


unsigned int a, b;
std::cin » a » b;
unsigned int x = a ^ b;

Your patience was wearing thin: "Professor, everyone knows that this is equal to the bitwise exclusive OR, more commonly known as XOR, of two numbers, and not the power of them. Can you please give us something more interesting?"

"Sure, {username}, I'm aware that you know this, but there are certain things I have to teach anyway," responded the professor. "I have a related problem for you to solve, though. Write a program that, given an unsigned 32-bit integer $$$a$$$, produces all unsigned 32-bit integers $$$b$$$ such that the power $$$a^b$$$ and the bitwise exclusive OR $$$a \oplus b$$$ are the same modulo $$$2^{32}$$$. This also means their unsigned 32-bit integer representations are the same, and you'll help us find when the code from my presentation is correct."

For the purposes of this problem, please consider that $$$0^0$$$ is equal to $$$1$$$, as if you were calculating powers of a number by multiplying $$$1$$$ with that number multiple times.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 100\,000$$$). The description of the test cases follows.

The only line of each test case contains a single integer $$$a$$$ ($$$0 \le a \le 2^{32} - 1$$$): the value given by professor Claudio.

Output

For each test case, print one line. First, print the number $$$k$$$ of different suitable values of $$$b$$$ (that is, for which $$$a^b - (a \oplus b)$$$ is divisible by $$$2^{32}$$$). Next, if $$$k \gt 0$$$, print all the different values on the same line in ascending order. The values should be integers between $$$0$$$ and $$$2^{32} - 1$$$.

Example
Input
2
6
2147483649
Output
0
1 2147483648