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 in which x ≥ 0. Help Peter to find them.

Input

The first line specifies the number of examples of t (0 < t < 21), which should be solved by Peter, and the subsequent t lines of the two numbers through the space: a and b (0 ≤ a, b ≤ 231).

Output

For each example, type in a separate line, one solution: the smallest possible positive value of x and corresponding integer value of y, or, in the absence of solutions, "No Solution".