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

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

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