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 г. Житомир