Hôm nay, noodles0428 học về dãy số Fibonacci. Cô ấy biết rằng đây là một dãy số rất đặc biệt vì nó gắn liền với nhiều ứng dụng thực tế trong đời sống của chúng ta.

Do rất hứng thú với dãy số này, cô ấy đã quyết định nghĩ ra một biến thể của dãy số Fibonacci - đó là dãy số XOR-nacci! Dãy số này như sau:

Gọi ~F_i~ được gọi là số XOR-nacci thứ ~i~.

~F_0 = 0~

~F_1 = 1~.

~F_i = F_{i-1} \oplus F_{i-2}~ với mọi ~i \ge 2~, và ~\oplus~ là phép ~XOR~ bit.

Yêu cầu: Nhiệm vụ của bạn là phải trả lời đúng toàn bộ ~q~ câu hỏi mà cô ấy đưa ra, tức là trả lời đúng tất cả giá trị ~F_n~ với ~n~ là giá trị mà noodles0428 cho.

INPUT

Dòng đầu tiên nhập vào số ~q~ (~1 \le q \le 10^5~) - với ~q~ là số câu hỏi mà noodles0428 đưa ra.

~q~ dòng tiếp theo, mỗi dòng nhập vào một giá trị ~n~ (~1 \le n \le 10^{12}~).

OUTPUT

Bạn cần in ra ~q~ dòng, mỗi dòng là một giá trị ~F_n,~ tương ứng với từng giá trị ~n~ mà noodles0428 cho.

SAMPLE INPUT

3
1
2
3

SAMPLE OUTPUT

1
1
0