Sáng sớm tinh mơ, iostream tỉnh giấc. Để có năng lượng cho cả một ngày dài, iostream sẽ làm một bữa sáng đủ chất dinh dưỡng. Bữa sáng của iostream gồm có ~n~ quả trứng luộc. Trong quá trình luộc trứng, iostream nghĩ ra một cách để luộc trứng chín đều nhất: trong giây thứ ~i~, cô sẽ lật những quả trứng có số thứ tự là bội của ~i~. Trứng sẽ chín hết sau ~n~ giây. iostream muốn hỏi các bạn, sau ~n~ giây, quả trứng thứ ~n~ sẽ úp hay ngửa? Cho biết, lúc đầu các quả trứng đều ở trạng thái ngửa.

Input

• Dòng đầu tiên của dãy chứa số nguyên dương ~t~ - số bộ test (~t \le 10~).
• ~t~ dòng tiếp theo, mỗi dòng chứa số ~n~, số trứng của iostream (~1 \le n \le 10^{18}~).

Output

• ~t~ dòng, mỗi dòng chứa trạng thái của quả trứng thứ ~n~. Nếu trứng úp thì in ra 1. Nếu trứng ngửa, in ra 0.

Sample Input

2
4
5

Sample Output

1
0

Subtask

• ~30\%~ số test có ~n \le 1000~.
• ~30\%~ số test tiếp theo có ~n \le 10^9~.
• ~40\%~ số test còn lại không có điều kiện gì thêm.