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,0,1,1,1,1,1,\ldots\). 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 \leq 100\)) - số câu hỏi;
• \(t\) dòng tiếp theo, mỗi dòng chứa số nguyên dương \(N\) (\(N \leq 10^{12}\)).

Output

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

Scoring

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

Example

2
5
6

1
0

Note

• Nguồn: Tin học trẻ bảng A (Tiểu học) năm 2023