Consider the infinite integer sequenceSstarting with:

S= 1, 1, 2, 1, 3, 2, 4, 1, 5, 6, 3, 7, 2, 8, 9, 4, 10, 1, 11, 12, ...

Circle the first occurrence of each integer.

S= ①, 1, ②, 1, ③, 2, ④, 1, ⑤, ⑥, 3, ⑦, 2, ⑧, ⑨, 4, ⑩, 1, ⑪, ⑫, ...

The sequence is characterized by the following properties:

• The circled numbers are consecutive integers starting with 1.
• Immediately preceding each non-circled numbers a_i, there are exactly ⌊log₂(1+a_i)⌋ adjacent circled numbers, where ⌊•⌋ is the floor function.
• If we remove all circled numbers, the remaining numbers form a sequence identical to S, so S is a fractal sequence.

Please find out then-th number in the sequenceS.

There are multiple test cases. The first line of input contains an integerTindicating the number of test cases. For each test case:

There is an integernin one line. (1≤n≤ 10¹⁵,T≤ 10000)

For each test case, print an integer indicating the answer in one line.

This problem was inspired by Problem 535 at Project Euler.

2015年宁波市大学生程序设计竞赛重现赛