В куче лежат $$$N$$$ камней. Два игрока по очереди делают ходы. На каждом ходе игрок может взять от $$$1$$$ до $$$K$$$ камней, но не может брать столько, сколько взял его соперник на предыдущем ходе. Тот, кто не сможет сделать ход, проигрывает. Определите, кто выиграет, если оба игрока действуют оптимально.
В первой строке входных данных вводится целое число $$$T$$$ — количество партий игры ($$$1 \le T \le 10$$$). В следующих $$$T$$$ строках вводятся по два целых числа $$$N_i$$$ и $$$K_i$$$ ($$$2 \le N_i \le 5000$$$, $$$2 \le K_i \le N_i$$$).
Для каждой партии выведите в отдельной строке 1, если выиграет первый игрок, и 2, если второй.
2 4 2 4 3
1 2
В примере при $$$N=4$$$, $$$K=2$$$ выиграет первый игрок. Он возьмёт один камень. Теперь у его соперника есть единственный ход — взять два камня, и затем первый игрок заберёт оставшийся камень.
При $$$N=4$$$, $$$K=3$$$ выиграет второй игрок. Если первый игрок возьмёт 1 или 3 камня, то второй возьмёт оставшиеся 3 или 1. Если же первый игрок возьмёт 2 камня, то второй возьмёт 1, и первому будет некуда ходить.
