Alice and Bob love to play Bomberman. They decided to upgrade the game. Their version is played on a rectangular board divided into cells. The first player puts a bomb on any cell. The bomb destroys this cell, as well as all consecutive undestroyed cells left, right, above and below it. Then the second player puts his bomb, then again the first and so on. The player who destroys the last cell wins the game. Given the dimensions of the board, determine which player wins the game assuming that both players play optimally.

Input

The first line contains T (1 <= T <= 1000) - the number of tests. The next T lines contain two integers m and n (1 <= m, n <= 100) - the size of the board.

Output

For each test print 1 if the first player wins the game, or 2 if the second wins.

Example

Input:
1
2 2

Output:
2

Example of the first two moves of 7x7 board