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