En unos trabajos arqueológicos recientes, se han encontrado restos de una hipotética civilización precolombina. Los restos encontrados apuntan a que dicha civilización utilizaba un método algo original para representar números, mediante dados. Los dados se disponen en bandejas divididas en porciones, numeradas consecutivamente de izquierda a derecha a partir del cero.
El número representado se calcula como la suma del valor de la cara visible de cada dado, ponderándolo adecuadamente según la porción de la bandeja que se encuentra: un dado que tenga el número X en la cara visible y que se encuentre en la posición de número r tiene como valor X*10^r (X multiplicado por 10 elevado a r). Por ejemplo, el número 1.024 puede representarse de las maneras siguientes (con dados de seis caras y una bandeja dividida en cuatro porciones):

(* figura 1 -ver la fotocopia recibida- *)

En la bandeja de la izquierda, la descomposición de 1.024 es 4*10^0 + 2*10^1 + 1*10^3, mientras que en la bandeja de la derecha tenemos 1.024 = 4*10^0 + 6*10^1 + 6*10^1 + 4*10^2 + 5*10^2.
Existen otras descomposiciones posibles.

Ahora bien, existe un fallo en este sistema de numeración: hay números que no pueden representarse. Por ejemplo, si disponemos de 2 dados de 6 caras, es imposible representar el número 17; no existe ninguna distribución de los dados que permita obtenerlo. Se pide un programa que calcule el menor número no representable con N dados de k caras, suponiendo que la bandeja está dividida en N porciones y que en cada porción caben N dados.

Entrada

Residente en el fichero de caracteres "DADO.DAT":
- Línea 1: un carácter (entre el '1' y el '9') que represente el número r de casos a resolver
- Líneas de la 2 a la r+1: cada línea representa un caso y está formada por: la representación con caracteres del número N de dados disponibles, a continuación un único carácter blanco, y por último la codificación en caracteres del número k de caras de los dados

Salida

A guardar en el fichero de enteros "DADO.OUT":
- r líneas (una para cada caso a tratar); cada línea contiene la solución del caso correspondiente, y será un número entero precedido de un blanco y no precedido de signo.

Ejemplo de entrada

4
2 6
3 6
2 4
3 4

Ejemplo de salida

17
77
9
19