Economic Game "P&T"

Given two non-negative integers A and B, two players—Supplier (S) and Transit (T)—engage in a strategic game where S always takes the first turn. During each move, a player must subtract a natural number, which is a multiple of the smaller number, from the larger number, ensuring the result remains non-negative. The player who cannot make a move loses the game.

Input

The first line contains the number of test cases 1 ≤ N ≤ 10. Each of the following N lines contains two integers, A and B (A, B < 2·10^9).

Output

Output a single line consisting of a sequence of N digits, either 1 or 2, written consecutively without spaces. Here, 1 indicates that S won, and 2 indicates that T won.

Examples