Simple equation

Simple equation

Peter found in a book a simple mathematical equation: a * x + b * y = 1.

His interest is only integral solutions of this equation, and only those in which x0. Help Peter to find them.


The first line specifies the number of examples of t (0 < t < 21), which should be solved by Peter, and the subsequent t lines of the two numbers through the space: a and b (0a, b231).


For each example, type in a separate line, one solution: the smallest possible positive value of x and corresponding integer value of y, or, in the absence of solutions, "No Solution".

Time limit 1 seconds
Memory limit 128 MiB
Input example #1
77 51
10 44
34 79
Output example #1
2 -3
No Solution
7 -3
Source Stage III All-Ukrainian Olympiad 2009-2010 Zhitomir