BIT2 - Search Bit Sum

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 didn't have enough dollars with him to buy this teddy. But there was a scheme ongoing like solve a equation and get the teddy and pay whatever we wish. Thats why this shop is weirdo. He had no eager to buy this teddy as not many 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 test cases. For each test case, 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

ID RESULT TIME
code...



Added by:Rishav Goyal
Date:2014-02-07
Time limit:1.223s-2.446s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:own

hide comments
2014-06-17 04:03:17 [Lakshman]
@Ujjwal Prakash I got Accepted with
(log(n)^2).
2014-06-17 04:03:17 Bhavik
huh..from sigkill,tle,sigsegv,wrong answer..to AC...:))

Last edit: 2014-02-14 19:51:37
2014-06-17 04:03:17 anurag garg
finally AC
2014-06-17 04:03:17 Mostafa 36a2
Yes! the worst solution again :D
2014-06-17 04:03:17 govihuu
Wow. Enjoyed it :D
2014-06-17 04:03:17 Rishav Goyal
Sorry & Thanks to all.
Once again the problems has been moved to classic with few changes in terms of reduces the time limit. sorry for deleting the comments as it reduces the dedication.
2014-06-17 04:03:17 Rishav Goyal
@Ujjwal

log(n) sol exists!
2014-06-17 04:03:17 Rishav Goyal
new test file has been added! so all the solutions has been rejudged!
2014-06-17 04:03:17 Ujjwal Prakash
The time limit is too strict
even (log(n)^2) is resulting to TLE

Last edit: 2014-02-08 08:11:46
2014-06-17 04:03:17 Jacob Plachta
Yup, the data is fine now, though the time limit seems very strict (but doable). More useful sample cases would be nice, though...

Edit: Thanks for the changes!

Last edit: 2014-02-07 16:55:19
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.