Two players are playing a game of Tower Breakers! Player $1$ always moves first, and both players always play optimally.The rules of the game are as follows:   

Initially there are $n$ towers.
Each tower is of height $m$.   
The players move in alternating turns. 
In each turn, a player can choose a tower of height $x$ and reduce its height to $y$, where $1\leq y<x$ and $y$ evenly divides $x$.  
If the current player is unable to make a move, they lose the game.   

Given the values of $n$ and $m$, determine which player will win. If the first player wins, return $1$.  Otherwise, return $2$.  

Example. 
$n=2$ 

$m=6$    

There are $2$ towers, each $6$ units tall.  Player $1$ has a choice of two moves: 

- remove $3$ pieces from a tower to leave $6$ as $6 \quad modulo \quad 3=0$ 

- remove $5$ pieces to leave $1$   

Let Player $1$ remove $3$. Now the towers are $3$ and $6$ units tall.

Player $2$ matches the move. Now the towers are both $3$ units tall. 

Now Player $1$ has only one move. 

Player $1$ removes $2$ pieces leaving $1$.  Towers are $1$ and $2$ units tall. 

Player $2$ matches again.  Towers are both $1$ unit tall.  

Player $1$ has no move and loses. Return $2$.

Function Description  

Complete the towerBreakers function in the editor below.   

towerBreakers has the following paramter(s):  

int n: the number of towers  
int m: the height of each tower  

Returns  

int: the winner of the game   

Input Format

The first line contains a single integer $t$, the number of test cases. 

Each of the next $t$ lines describes a test case in the form of $2$ space-separated integers, $n$ and $m$.  

Constraints

$1\leq t\leq100$
$1\leq n,m\leq10^6$

Sample Input
STDIN   Function
-----   --------
2       t = 2
2 2     n = 2, m = 2
1 4     n = 1, m = 4

Sample Output
2
1

Explanation

We'll refer to player $1$ as $P1$ and player $2$ as $P2$

In the first test case, $P1$ chooses one of the two towers and reduces it to $1$. Then $P2$ reduces the remaining tower to a height of $1$. As both towers now have height $1$, $P1$ cannot make a move so $P2$ is the winner.

In the second test case, there is only one tower of height $4$. $P1$ can reduce it to a height of either $1$ or $2$. $P1$ chooses $1$ as both players always choose optimally. Because $P2$ has no possible move, $P1$ wins.