P2609 [ZJOI2012] Sequence

Xiaobai and Xiaolan are in a math class together. After class, the teacher assigns a homework problem: find the general term of the following sequence: $$a_0=0,a_1=1,a_{2i}=a_i,a_{2i+1}=a_i+a_{i+1}$$ As a math enthusiast, Xiaobai quickly figures out the general term of this sequence. Xiaobai tells Xiaolan that he has solved it, but to prevent Xiaolan from copying, he does not want to reveal the formula. To show off while proving that he indeed solved it, Xiaobai comes up with a clever method: Xiaolan says a positive integer $n$, and Xiaobai tells the value of $a_n$. If Xiaobai can still quickly give the correct answer when $n$ is very large, it proves that he really has the formula. However, this method has a big flaw: Xiaolan cannot solve the problem himself, so he cannot verify whether Xiaobai’s answer is correct. As Xiaolan’s friend, can you help him?

The first line of input contains exactly one positive integer $T$, the number of test cases. The next $T$ lines each contain an integer $n$.

For each test case, output a single integer representing $a_n$ on one line.

- For 20% of the testdata, $1 \le n \le 10^8$. - For 50% of the testdata, $1 \le n \le 10^{12}$. - For 100% of the testdata, $1 \le T \le 20$, $1 \le n \le 10^{100}$. Translated by ChatGPT 5