Después de jugar incontables partidas del clásico problema de Josephus, OCI-kun y JOI-kun se aburrieron. Para hacer las cosas más interesantes, decidieron inventar un nuevo rompecabezas inverso basado en el mismo juego. El juego que están analizando funciona estrictamente con las siguientes reglas:

• Hay ~n~ participantes formando un círculo, numerados en sentido horario del ~1~ al ~n~.
• El turno avanza alrededor del círculo en ese mismo orden, comenzando siempre por el participante ~1~.
• De forma alternada, un participante permanece en el círculo y el siguiente participante lo abandona (es decir, el participante ~1~ se queda, el participante ~2~ se va, el participante ~3~ se queda, el participante ~4~ se va, etc.).
• El proceso da tantas vueltas como sea necesario y continúa hasta que solo queda un participante en el círculo, quien en su turno también lo abandona.

Por ejemplo, considera la siguiente situación donde ~n = 7~. En este caso, los participantes abandonan el círculo en el siguiente orden: ~2, 4, 6, 1, 5, 3, 7~.

Para hacer el rompecabezas más personal, deciden imaginarse a sí mismos dentro del círculo. JOI-kun asume la posición inicial del participante ~a~ y OCI-kun toma la posición inicial del participante ~b~. A ambos les gustaría terminar su participación al mismo tiempo para poder irse juntos a resolver problemas del último concurso Esperanzas Olímpicas. Por lo tanto, quieren asegurarse de que OCI-kun (el participante ~b~) abandone el círculo inmediatamente después de JOI-kun (el participante ~a~).

Dadas sus posiciones iniciales ~a~ y ~b~, tu tarea es encontrar el menor número total de participantes ~n~ que deben formar el círculo para que logren abandonar el juego de forma consecutiva.

Entrada

La primera línea contiene un único entero ~t~ (~1 \le t \le 10^5~) ~-~ el número de casos de prueba.

Cada una de las siguientes ~t~ líneas contiene dos enteros ~a~ y ~b~ (~1 \le a, b \le 10^6~) ~-~ las posiciones de JOI-kun y OCI-kun, respectivamente.

Salida

Para cada caso de prueba, imprime un único entero ~-~ el menor tamaño posible del círculo ~n~. Si no existe ninguna solución válida, imprime ~-1~.

Subtareas

Subtarea	Puntos	Restricciones adicionales	Dependencias
~1~	~5~	~1 \le t \le 1000~, ~1 \le a, b \le 100~	~-~
~2~	~8~	~1 \le t \le 1000~, ~1 \le a, b \le 1000~	~1~
~3~	~10~	~1 \le t \le 1000~, ~1 \le a, b \le 10^6~, ~a \equiv 0 \pmod{2}~	~-~
~4~	~29~	~1 \le t \le 1000~, ~1 \le a, b \le 10^6~, ~a < b~	~-~
~5~	~37~	~1 \le t \le 1000~, ~1 \le a, b \le 10^6~	~1-4~
~6~	~11~	Sin restricciones adicionales	~1-5~

Ejemplos

Entrada 1

10
1 3
2 1
2 2
2 3
2 4
2 5
3 1
3 7
42 44
1337 17

Salida 1

3
2
-1
-1
4
-1
4
7
44
1344