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ò choi 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.

Đầu vào

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.

Đầu ra

Ứ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 ≤ T ≤ 100; 0 ≤ N ≤ 10⁶