Giải bài trực tuyến

Người hành tinh BrainPower vừa mời Nuga tham dự một cuộc thi đấu thú vị. Đó là giải “Cờ Chạy” liên hành tinh.

“Cờ Chạy” là thể loại cờ do Co & Da – người hành tinh BP đưa ra vào năm 3101. Mỗi ván có 2 người chơi, luân phiên nhau thực hiện nước đi của mình, bốc thăm để chọn người chơi trước. Bàn cờ là một dãy N ô vuông, đánh số từ 1 đến N từ trái sang phải, và chỉ có 2 quân cờ duy nhất, ban đầu được đặt ở 2 ô vuông do 2 người chơi tự do lựa chọn (hai ô vuông này có thể trùng nhau). Giả sử 2 quân cờ đang ở 2 ô vuông có chỉ số là X và Y ( X ≤ Y). Người chơi thực hiện nước đi bằng cách di chuyển quân cờ ở vị trí Y đi K ô về bên trái, sao cho K phải là một bội số dương của X, và quân cờ vẫn ở trên bàn cờ. Nói cách khác, vị trí mới của quân cờ Y là Y’ = Y – K, Y’ ≥ 1. Trò chơi kết thúc khi không thể thực hiện được nước đi nào nữa. Và người không thực hiện được nước đi của mình là người thua cuộc.

Cuộc thi có nhiều vòng, mỗi vòng gồm các cặp đấu loại trực tiếp. Người thắng được lọt vào vòng trong. Người thắng trong tất cả các trận, tất nhiên, trở thành Nhà vô địch, và được thưởng 100 Triệu USD.

Nuga rất muốn giành được số tiền khổng lồ này vì cô bé đang có ý định tân trang lại con tàu siêu tốc của mình. Những người tham gia trò chơi đều là những bộ óc vĩ đại đến từ các hành tinh khác nhau, họ đều chơi tối ưu cho mọi nước đi, vì thế, Nuga phải chuẩn bị trước một số khả năng chọn ô ban đầu đặt quân cờ sao cho mình chắc chắn thắng. Cho một loạt cặp 2 số X, Y là chỉ số của 2 ô vuông ban đầu đặt 2 quân cờ. Bạn hãy giúp Nuga xác định xem Nuga phải đi trước hay đi sau thì chắc chắn sẽ thắng?

(P/S: Nuga hứa sẽ chia cho bạn một nửa giải thưởng nếu Vô địch! :P)

Dữ liệu

Gồm nhiều dòng, mỗi dòng ghi 2 số nguyên dương X Y. Kết thúc bằng cặp số 0 0.

Kết quả

Tương ứng với mỗi X Y, ghi ra trên một dòng, T nếu Nuga phải đi trước, S nếu Nuga phải đi sau để chắc chắn thắng.

Giới hạn

• X, Y ≤ 2^31 – 1
• Trong 50% số điểm, có X, Y ≤ 1000
• Thời gian: 1s

Ví dụ

Dữ liệu:
1 1
9 2
0 0


Kết quả:
S
T