Problems
Simple equation
Simple equation
Peter found in a book a simple mathematical equation: a \cdot x + b \cdot y = 1.
His interest is only integral solutions of this equation, and only those for which x \ge 0. Help Peter to find them.
Input data
The first line contains the number of test cases t~(0 < t < 21). Each of the next t lines contains two integers a and b~(0 \le a, b \le 2^{31}).
Output data
For each test case print in a separate line one solution: the smallest possible non-negative value of x and corresponding integer value of y. In case if there is no solution, print "No Solution".
Examples
Input example #1
3 77 51 10 44 34 79
Output example #1
2 -3 No Solution 7 -3