eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Просте рівняння

Просте рівняння

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

Петрик знайшов у книжці просте математичне рівняння: a \cdot x + b \cdot y = 1.

Його цікавлять лише цілочисельні розв’язки цього рівняння і лише ті, у яких x \ge 0. Допоможіть Петрику їх знайти.

Вхідні дані

Перший рядок містить кількість тестів t~(0 < t < 21). Кожний з наступних t рядків містить два числа a та b~(0 \le a, b \le 2^{31}).

Вихідні дані

Для кожного тесту виведіть в окремому рядку один розв’язок рівняння: мінімально можливе невід’ємне значення x та відповідне для нього ціле значення y. У випадку відсутності розв’язку виведіть "No Solution".

Приклад

Вхідні дані #1
3
77 51
10 44
34 79
Вихідні дані #1
2 -3
No Solution
7 -3
Джерело III етап Всеукраїнської олімпіади 2009-2010 м. Житомир