Two piles once...

Misha divided a certain number of cones into two piles, containing A and B cones respectively, and proposed a game to Masha. The rules are simple: on each turn, a player can take any number of cones, but only from one pile. The player who takes the last cone wins. Masha always makes the first move.

Your task is to determine, for given values of A and B, which player will win if both play optimally.

Input

The first line contains the number of test cases N (1 ≤ N ≤ 10^5). Each of the following N lines contains two non-negative integers A and B, each not exceeding 2 10^9.

Output

Output a single line containing a sequence of N digits, either 1 or 2, indicating the player who will win with optimal play for each test case.

Examples