Matcom Online Grader

Los héroes de inteligencia del DOTA están jugando un juego (que se juega entre dos jugadores) contra los héroes de fuerza.

Para jugar en cada partida se toma una barra de chocolate que tiene dimensiones NxM, o sea contiene N*M cuadritos de tamaño 1x1. Los jugadores juegan alternadamente, en un turno un jugador puede coger la barra de chocolate, partirla en dos barras (cada una que contenga al menos un cuadradito 1x1) y comerse una de ellas. Para partir la barra solo lo pueden hacer como normalmente se parte una barra de chocolate, por una línea vertical o por una línea horizontal. El jugador al que le toque jugar y la barra sea un cuadradito de 1x1 pierde.

Los héroes de inteligencia quiren ganarle siempre a los de fuerza, así que Fito los va a ayudar. Dadas las dimensiones de la barra, Fito les va a decir si en cada partida el jugador de inteligencia debe ser el primero o el segundo en jugar.

Input

Un entero 1<=T<=1000 que representa la cantidad de casos.

Cada caso será una línea con 2 enteros 1 <= N,M <= 10^18 que serán las dimensiones de la barra.

Output

Por cada caso una línea que contenga “1” si los héroes de inteligencia deben ser los primeros y “2” en caso contrario.

Sample test(s)

Hints

En el segundo caso si en cada partida el jugador de inteligencia elige jugar segundo, el de fuerza va a perder porque cuando le toca jugar la barra es un cuadradito de 1x1