eolymp
bolt
Try our new interface for solving problems
Problems

Simple equation

Simple equation

Time limit 1 second
Memory limit 128 MiB

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
Source Stage III All-Ukrainian Olympiad 2009-2010 Zhitomir