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 for which x≥0. Help Peter to find them.
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≤a,b≤231).
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".