Ys và NN đang chơi 1 trò chơi có tên gọi là TowerDiv. Trò chơi này có luật như sau
Ban đầu sẽ có N tòa tháp, mỗi tòa tháp ban đầu đều có độ cao là M
Tại mỗi lượt chơi luân phiên, người chơi có thể chia đều 1 tòa tháp bất kỳ trong N tòa tháp thành các phần có chiều cao là nguyên dương bằng nhau (ít nhất chia ra làm 2 phần trở lên), Người chơi phải lấy ra tất cả các phần phía trên, chỉ chừa lại duy nhất 1 phần ở dưới đáy, lúc này chiều cao của tòa tháp sẽ giảm đi 1 lượng đúng với tổng chiều cao của số phần đã lấy ra.
Ví dụ, chiều cao hiện tại của tòa tháp được Ys chọn đang là 6, Ys có thể chia tòa tháp làm 3 phần, mỗi phần có kích thước là 2, Theo quy định, Ys phải lấy đi 2 phần trên cùng và chỉ giữ lại 1 phần dưới đáy. Vì vậy chiều cao của tòa tháp hiện tại sẽ còn là 2.
Trò chơi chỉ kết thúc khi có 1 người không thể thực hiện được bước ở trên như đã quy định, và người đó sẽ thua.
Vì Ys muốn nhường NN nên để cho NN đi trước. Giả sử 2 người đều chơi tối ưu, hãy xác định người thắng cuộc.
Input:
– Dòng đầu tiên chứa 1 số T là số bộ test (T<=100)
– T dòng tiếp theo, mỗi dòng chứa lần lượt 2 số N và M (N, M<=106)
Output:
– Tương ứng mỗi bộ test, in ra 1 nếu NN thắng, in ra 2 nếu Ys thắng.
Ví dụ
Input:
2
2 2
1 4
Output:
2
1
Giải thích:
Ở test 1, n=2,m=2
– Lượt đầu tiên, NN có thể chọn 1 trong 2 tòa tháp và chia nó ra làm 2 và giữ lại phần đáy.
Đương nhiên, dù chọn tòa tháp nào thì cũng sẽ còn lại 1 tòa tháp có chiều cao là 2.
Lúc này chiều cao 2 tòa tháp lần lượt sẽ là: 1 2
– Lượt tiếp theo, Ys chỉ cần chia tòa tháp còn lại có chiều cao 2 đó ra làm 2 và giữ lại phần đáy.
Lúc này chiều cao của 2 tòa tháp là : 1 1
– Lượt thứ 3, NN không thể chia được tòa tháp nào bởi vì cả 2 đều đã bằng 1.
Vì vậy người chiến thắng là Ys.