¿Hoy te sientes motivado? Tu progreso seguro que hasta ahora es bueno. En Coderperu no siempre hacemos las misma cosas. Hoy y ahora vamos a ver algo de matemática. Pero tranquilo! Este problema es muy sencillo, aunque como buen programador podrás con esta pequeña interrogante.

Dado tres enteros 0 <= X <= 10000, 0 <= Y <= 10000, 0 <= K <=4 debes determinar el indice K de pow(X, Y) "Potencia" donde el indice 0 esta mas a la derecha. Por ejemplo:

Para X = 2, Y = 10, K = 1 donde pow(2, 10) = 1024 retornar 2.

Si no hay un digito en la posicion K retornar -1.

Input

La primera línea del INPUT comienza con un número M que indica el número de casos del problema propuesto. (1 ≤ M ≤ 50)

Cada caso está compuesto de la(s) siguiente(s) linea(s):

Una sola línea para cada caso contiene los enteros X, Y, K. Los elementos necesarios para la operación de turno.

Restricciones.

1 ≤ X ≤ 10000
1 ≤ Y ≤ 10000
1 ≤ K ≤ 4

Output

Salida para cada caso. retornar el valor de K en la potencia.

Entrada de ejemplo