Задача Girls. У Даринки та її подруги Тетянки є число n. Уявімо собі його запис у системі числення з основою k. Дівчата грають у гру з такими правилами:

 

1) За один хід можна зменшити будь-який розряд запису числа у системі числення з основою k на будь-яке ціле значення від 1 до r, але так, щоб значення розряду не стало менше нуля.

2) Перемагає дівчинка, після ходу якої число перетвориться у нуль.

Визначте, хто з дівчат переможе при оптимальній грі обох. Гравці ходять по черзі, перший хід робить Даринка.

Технічні умови. Програма читає з клавіатури натуральне число t (1≤t≤500) - кількість тестових наборів. Наступні t рядків містять по 3 числа, записані через пропуск - початкове число n (1≤n≤1018), основу системи числення k (2≤k≤1018) та r (1≤r≤1018). Програма виводить екран t рядків, кожен з яких повинен містити число 1, якщо переможе Даринка, або 2, якщо переможе Тетянка.

Приклад

Введення

3

123 10 4

7 2 2

48 10 3

Виведення

2

1

2

© LIKT 1998-2018