我能获得这个Plzzz的代码吗？ [英] Can I Get The Code For This Plzzz

问题描述

0/1 string是一个字符串，其中每个字符都是0或1.有两个操作可以在0/1字符串上执行：



开关：每0变为1，每1变为0.例如，100变为011。

reverse：字符串反转。例如，100变为001。

考虑这个0/1字符串的无限序列：



S0 =< br $>


S1 =0



S2 =001



S3 =0010011



S4 =001001100011011



。 ..



SN = SN-1 +0+开关（反向（SN-1））。



您需要弄清楚Sgoogol的Kth字符，其中googol = 10100.



输入



输入的第一行给出了测试用例的数量T.每个下一个T行包含一个数字K.



输出



对于每个测试用例，输出一行包含Case #x：y，其中x是测试用例编号（从1开始），y是Sgoogol的第K个字符。



限制



1≤T≤100

小数据集



1≤K≤105。

大数据集


1≤K≤1018。

样品





输入


输出



4

1

2

3

10



案例＃1：0

案例＃2： 0

案例＃3：1

案例＃4：0

A "0/1 string" is a string in which every character is either 0 or 1. There are two operations that can be performed on a 0/1 string:

switch: Every 0 becomes 1 and every 1 becomes 0. For example, "100" becomes "011".
reverse: The string is reversed. For example, "100" becomes "001".
Consider this infinite sequence of 0/1 strings:

S0 = ""

S1 = "0"

S2 = "001"

S3 = "0010011"

S4 = "001001100011011"

...

SN = SN-1 + "0" + switch(reverse(SN-1)).

You need to figure out the Kth character of Sgoogol, where googol = 10100.

Input

The first line of the input gives the number of test cases, T. Each of the next T lines contains a number K.

Output

For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y is the Kth character of Sgoogol.

Limits

1 ≤ T ≤ 100.
Small dataset

1 ≤ K ≤ 105.
Large dataset

1 ≤ K ≤ 1018.
Sample


Input

Output

4
1
2
3
10

Case #1: 0
Case #2: 0
Case #3: 1
Case #4: 0

推荐答案

否。

我们不做你的功课：这是有原因的。它就是为了让你思考你被告知的事情，并试着理解它。它也在那里，以便您的导师可以识别您身体虚弱的区域，并将更多的注意力集中在补救措施上。



亲自尝试，你可能会发现它不是和你想的一样困难！



如果遇到具体问题，请询问相关问题，我们会尽力提供帮助。但我们不打算为你做这一切！

No.
We do not do your homework: it is set for a reason. It is there so that you think about what you have been told, and try to understand it. It is also there so that your tutor can identify areas where you are weak, and focus more attention on remedial action.

Try it yourself, you may find it is not as difficult as you think!

If you meet a specific problem, then please ask about that and we will do our best to help. But we aren't going to do it all for you!

这篇关于我能获得这个Plzzz的代码吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！