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. \InputFile 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})$. \OutputFile 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 "\textbf{No Solution}".