Breaking Plates

Eleni and Petros have in front of them two piles of plates. One pile has ~N1~ plates and the other has ~N2~ plates. The game proceeds as follows: players take turns either taking one plate from one pile and breaking it or taking two plates (one from each pile) and breaking them. The player who breaks the last plate wins. Eleni always starts the game. Given ~N1~ and ~N2~, your program should determine whether the starting player (Eleni) wins or the second player (Petros) wins.

Input

A file named dishes.in contains an integer ~M~ on the first line (~0 < M \le 1.000~) indicating the number of repetitions. Then, ~M~ pairs of numbers follow, each indicating the number of plates in the two piles, ~N1~ and ~N2~ (~0 < N1, N2 \le 1.000~). These two numbers are separated by a single space.

Output

A file named dishes.out containing ~M~ integers (one integer per line). The integer is ~1~ if Eleni wins and ~2~ if Petros wins. The output file should end with a newline character.

Examples

• For ~N1 = 1~ and ~N2 = 1~, it is obvious that Eleni wins (she breaks both plates and finishes).
• For ~N1 = 2~ and ~N2 = 2~, it is obvious that Eleni loses. Why: If Eleni breaks one plate from each pile, then Petros breaks the remaining two plates (one from each pile). If Eleni breaks one plate from one pile, then Petros breaks the other plate from the same pile, and then Eleni has only one option left to break one from the pile with two plates, and Petros breaks the other, winning.
• If ~N1 = 2~ and ~N2 = 3~, Eleni wins. Why: Eleni breaks one plate from the pile with three plates, and Petros plays with piles of ~N = 2~ and ~M = 2~. However, according to the previous example, the player who starts with piles of ~N = 2~ and ~M = 2~ always loses (thus Petros loses).

Example of Input - Output Data

STDIN (dishes.in)

2
2 3
2 2

STDOUT (dishes.out)

1
2

Maximum execution time: ~1~ sec.