\(Kaninho\) có \(n\) bóng đèn được xếp thành một hàng ngang và chúng được đánh số từ \(1\) đến \(n\). Ban đầu, tất cả các bóng đèn đều tắt và \(Kaninho\) có \(n\) thao tác thực hiện trên các bóng đèn như sau:

• Ở thao tác thứ \(i(1\le i\le n)\), những bóng đèn nào có chỉ số chia hết cho \(i\) sẽ đảo trạng thái (tức là từ bật sang tắt hoặc ngược lại)

Hỏi sau khi thực hiện xong \(n\) thao tác, bóng đèn thứ \(n\) có trạng thái gì ? Nếu bóng đèn thứ \(n\) ở trạng thái bật ta in ra \(1\) ngược lại in ra \(0\)

Input:

• Dòng thứ nhất chứa số \(t(1\le t\le 50)\) thể hiện số testcase

• \(t\) dòng tiếp theo, mỗi dòng chứa số nguyên dương \(n(1\le n\le 10^5)\)

Output:

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

Ví dụ:

Input:

1
4

Output:

1

Giải thích:

• Ban đầu ta có \(4\) bóng đèn ở trạng thái như sau: \(0,0,0,0\)

• Sau phép toán thứ \(1\): \(1,1,1,1\)

• Sau phép toán thứ \(2\): \(1,0,1,0\)

• Sau phép toán thứ \(3\): \(1,0,0,0\)

• Sau phép toán thứ \(4\): \(1,0,0,1\)

Do đó đáp án là \(1\)

Subtask:

• \(37,5\text{%}\) : $1\le n\le 20 $

• \(62,5\text{%}%\) : Không có điều kiện gì