El gabinete de ministros ha decidido que todos los numero de las puertas de las  oficina en los ministerios deben ser número primo de cuatro dígitos.

Periódicamente deben cambiar los números de las puertas, y se desea gastar lo menos posible para realizar estos cambios.

Parece muy simple, cambiemos un solo numero y al parecer tenemos una solución. Veamos por ejemplo el numero primo $1033$ si cambiamos el primer dígito por $8$ obtenemos el numero $8033$ que no es primo, razón por la cual no es un cambio valido.

Por motivos de seguridad no es posible que exista un numero no primo en la puerta, ni siquiera por algunos segundos. Por lo tanto se requiere un camino de números primos por el cual el numero $1033$ se pueda cambiar al $8179$ donde se cambia un solo dígito para pasar de un número primo a otro.

Ahora el ministro de finanzas interviene, y dice que es un gasto innecesario. Conoce que el costo de cambiar un dígito es de un boliviano. Dado este requerimiento le piden hallar el camino mas barato para cambiar de un numero primo a otro.

Halle el camino de números primos más barato entre dos números primos de cuatro dígitos. Tome en cuenta que los primeros $4$ dígitos no deben ser ceros.

Para el ejemplo la secuencia de números primos es la siguiente: $1033$, $1733$, $3733$, $3739$, $3779$, $8779$, $8179$.

El costo de esta solución es de $6$ bolivianos. Vea que el dígito $1$ que se cambio en el paso $2$ no puede reutilizarse en el último paso: se debe comprar uno nuevo.

La entrada comienza con una linea que contiene un numero positivo que el indica el numero de casos de prueba. Luego siguen los casos de prueba cada uno en una línea consistente en dos números primos de cuatro dígitos separados por un espacio.

Escriba por cada caso de prueba una linea con el numero mínimo de costo o la palabra Imposible.