Mèo Tom và chuột Jerry đang chơi một trò chơi để phân định, ai thắng sẽ được lấy miếng phô mai cuối cùng trong tủ lạnh. Trò chơi như sau: Cho một số nguyên dương ~N~, hai người chơi luân phiên. Tom chơi trước, ai tới lần chơi, sẽ phải tìm một số nguyên ~a(a \lt N)~ là ước của ~N~, sau đó ~N~ sẽ bị trừ đi ~a~. Ai không tìm được số ~a~ nữa sẽ là người thua cuộc. Cho biết số ~N~, bạn hãy xác định Tom hay Jerry thắng.

Dữ liệu:

• Dòng đầu tiên của đầu vào chứa số nguyên ~T~ cho biết số bộ dữ liệu cần kiểm tra. Mỗi bộ dữ liệu gồm một dòng chứa số nguyên ~N~.

Kết quả:

• Ứng với mỗi bộ dữ liệu đầu vào, chương trình của bạn cần in ra một dòng chứa số ~1~ nếu Tom thắng hoặc số ~0~ nếu Jerry thắng.

Ràng buộc

• ~1 \leq T \leq 100 ; 1 \leq N \leq 10^6~.

Ví dụ:

Sample Input

2
2
4

Sample Input

1
1