Пусть есть некоторое число N. За одну операцию каждому игроку позволяется делить данное число нацило (обычное деление с удалением дробной части результата) на любое число, не меньше за 2 и не больше за M. Проигрывает тот кто получит в результате 0. Игроки ходят по очереди. Найдите кто выигрывает, при оптимальной игре каждого из игроков. Технические вимоги:Обмеження времени: 1 секунду Формат входных данных: в первой строке входного файла GAME.IN содержится единственное число К (1 ≤ K ≤ 10000) – количество тестовых блоков в файле. В каждой следующей строке содержится один тестовый блок, который состоит из двух целых чисел N и M, 2 ≤ N ≤ 1000000000 и 2≤ M ≤ N. Формат выходных данных: в файл GAME.OUT для каждого из тестовых блоков в отдельной строке выведите 1, если при данных N и M выигрывает первый игрок, и 2 - если второй. Пример входных и выходных данных:
Game.in
2
5 3
10 4
Game.out
1
2
Game.in
2
5 3
10 4
Game.out
1
2