Deepan is a palantir incredible guy who once had a trip in Switzerland. He saw a weird shop where he liked a teddy. But he din have enough dollars with him to buy this teddy. But there was a scheme ongoing like solve a equation and get the teddy && pay whatever we wish.Thats why this shop is weirdo. He had no eager to buy this teddy as not much of people can solve the equation, so he was sure he can get this teddy as soon as he solve the problem. He need your help to solve the equation. You will be given a number N, and you have to tell whether there exist a number K so that sum of BITS in all the numbers from 1 to K is equal to N. If there exist a K, then print it, else print "Does Not Exist." without quotes.

Constraints

1 <= N <= 10^15, 1 <= T <= 10^5.

Input

First line contains t, number of testcases. For each testcase, first line contains N.

Output

Output as described above.

Example

Input:
6
282657
377636
472615
567594
662573
1992279
Output:
38050
49299
Does Not Exist.
Does Not Exist.
82953
227394