Cho dãy số có quy luật sau: ~0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, …~ Hãy xác định vị trí thứ ~N~ của dãy số trên là số ~0~ hay số ~1~?

Input

• Dòng thứ nhất chứa ~t~ (~t \le 100~) - số câu hỏi;
• ~t~ dòng tiếp theo, mỗi dòng chứa số nguyên dương (~N \le 10^{12}~).

Output

• Ứng với mỗi câu hỏi, in ra đáp án cần tìm.

Scoring

• Subtask 1 (1/3 số test): ~N≤10^3~;
• Subtask 2 (còn lại): không ràng buộc gì thêm.

Sample Input

2
5
6

Sample Output

1
0