SH08-200 Tom and Jerry Tom và 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 1 số nguyên dương N, Tom và Jerry chơi luân phiên, Tom sẽ được đ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ẽ thua cuộc. Cho biết số nguyên N hãy xác định Tom hay Jerry thắng Mô tả đầu vào Dòng 1 ghi số nguyên T là số bộ Test T dòng tiếp theo, mỗi dòng ghi số nguyên N Ràng buộc 1\leq T \leq 100; 1\leq N \leq 10^61≤T≤100;1≤N≤10 6 Mô tả đầu ra T dòng ghi số: 1: Nếu Tom thắng 0: Nếu Jerry thắng Hướng dẫn: • Nếu N=1 => Người chơi đầu thua • Nếu N=2 => Người chơi đầu thắng • Giả sử: N ban đầu chẵn => Người chơi đầu có thể chọn 1 trong 2 cách sau o Trừ N đi 1 vì 1 là ước của N o Trừ đi bất kì ước nào của N ( ngoài ước 1 và N)  Nếu chọn cách trừ 1 => N-1 là số lẻ => ước của (n-1) luôn là số lẻ => Người chơi 2 chọn bất kì ước nào đi nữa thì sau khi người 2 chơi đều cho 1 số N mới là một số chẵn (vì (n-1) lẻ - 1 số lẻ => cho kq chẵn)  Từ đây => Nếu N ban đầu chẵn thì người đi đầu luôn thắng. • Nếu N lẻ với tư tưởng trên bạn biết người nào chiến thắng rồi đấy • Nói dài dòng tóm lại là gì? Kết quả bài toán phụ thuộc vào n-1 là số chẵn hay lẻ???? (Vì sao) Test case mẫu Đầu vào mẫu 1 2 2 4 Đầu ra mẫu 1 1 1 C++ nha