Задачи
Простое уравнение
Простое уравнение
Петя нашёл в книге простое математическое уравнение: 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