A tourist gets lost in the desert with n liters of water. He drinks positive integer units of water each day.
Write a program to calculate how many different ways the tourist can drink up the water.
The first line contains the number of test cases $T(T\leq10)$.
Next $T$ lines contain the number $n(1\leq n\leq1000000)$ for each test case.
Output consists of $T$ lines.
Each line contains the binary number which represents number of different ways to finish up the water specified in the test case.