На столе лежат n спичек. Играют двое, ходят по очереди. За один ход игрок может взять не более m спичек, но не менее одной. Забравший последнюю спичку выигрывает.

Кто выиграет при правильной игре - первый или второй игрок?

Входные данные

В первой строке находится количество тестов t (1 ≤ t ≤ 100). Каждая из следующих t строк содержит количество спичек n в кучке и наибольшее разрешенное число спичек m для взятия за один ход. Известно, что 1 ≤ n, m ≤ 2 * 109.

Выходные данные

Вывести последовательность из t единиц и двоек: 1 - если при правильной игре выигрывает первый и 2 - если выигрывает второй.