Al perrito chill le gustan mucho las matematicas, pero sus amigos Sarce y Nerbyn les han preguntado ya mucho sobre la secuencia de Fibonacci, y prometen que este será el último problema de ese tipo. Ellos le hacen muchas preguntas del siguiente tipo: le dan dos números consecutivos de dicha serie (como pueden ser muy grandes solo le dan su resto al ser divididos por ~10^9+7~) y le piden cuál es la posición del menor par de números consecutivos que tienen dichos restos. En otras palabras, dado el par ~(F_n, F_{n+1})~ El perrito debe responder el menor ~n~ que cumpla que sus dos Fibonaccis consecutivos tengan dichos restos.

Nota:

Fibonacci es una recurrencia lineal (una función que utiliza valores de ella misma) definida por la ecuacion:

~F_n = F_{n-1} + F_{n-2}~

Conociendo que:

~F_0 = 0~

~F_1 = 1~

De esos valores iniciales se pueden formar los que les continúan:

~F_2 = F_1 + F_0 = 1~

~F_3 = F_2 + F_1 = 2~

~F_4 = F_3 + F_2 = 3~

Y así consecutivamente

Tarea

Ayuda a resolver las preguntas de sus profesores.

Entrada

La primera línea contiene un único entero ~q~, la cantidad de preguntas que le hacen al perrito chill.

A partir de ahí hay ~q~ líneas, cada una con dos enteros ~F_n~ y ~F_{n+1}~

Salida

Por cada consulta debes responder una línea con el índice/posición pedida. Se asegura que la respuesta a los casos dados es menor que ~10^9+7~.

Restricciones

~1 \le q \le 10^5~

~0 \le F_n , F_{n+1} < 10^9+7~

Subtareas

• (5pt) Solo hay una consulta y se asegura que la respuesta es menor o igual a ~10^8~.

• (10pt) Hay a lo más ~10~ consultas y la respuesta es menor o igual que ~10^6~.

• (15pt) La respuesta es menor o igual que ~10^5~.

• (20pt) La respuesta siempre será menor o igual que ~10^6~

• (50pt) ~1 \le q \le 20~

Ejemplo de entrada 1

5
0 1
1 1
1 2
2 3
3 5

Ejemplo de salida 1

0
1
2
3
4