Mèo Tom và chuột Jerry đang chơi một trò chơi để phân định, ai thắng sẽ 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 < 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 vào

• Dòng đầu tiên của đầu vào chứa số nguyên T cho biết bộ số 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ụ:

INPUT

   2
   2
   4

OUTPUT

   1
   1