El Dr. Lucas B-Tree trabaja con palabras grandes y sus propiedades, más precisamente propiedades palindrómicas.

Una palabra palíndromo es una palabra que se puede leer igual de izquierda a derecha y de derecha a izquierda: "aabcbaa" es palíndromo mientras que "aassab" no lo es; eso también significa que el primer carácter coincide con el último, y el segundo coincide con el anterior al último y así sucesivamente... más precisamente ~S~[~i~] = ~S~[~L - 1 - i~] para una cadena ~S~ indexada en base ~0~ de longitud ~L~. Decimos que el índice ~L - 1 - i~ es un espejo del índice ~i~, y viceversa, por lo tanto, definamos que son una pareja espejo; (nótese que si la palabra tiene una longitud impar, el índice ~L/2~ es un espejo de sí mismo). Obviamente en una palabra palíndromo todas las parejas espejo tienen el mismo valor.

Un casi palíndromo de grado ~K~ es una cadena ~S~ para la cual exactamente ~K~ parejas espejo tienen el mismo valor. Como un entero puede representarse como una cadena de caracteres, el Dr. B-Tree quiere encontrar cuántas cadenas de longitud ~L~, que constan solo de dígitos, son casi palíndromos de grado ~K~. También quiere que la respuesta se module con ~1000000007~ ~(10^9 + 7)~.

Entrada

La primera línea de entrada contiene un entero ~T~ ~(1 \leq T \leq 10^5)~ que indica el número de casos de prueba. Siguen ~T~ líneas, cada una de las cuales contiene dos enteros separados por espacios ~L~ ~(1 \leq L \leq 10^3)~ ​​y ~K~ ~(1 \leq K \leq 10^3)~ ​​que representan la longitud de las cadenas casi palíndromos y el número de pares de espejos que deberían tener respectivamente.

Salida

Para cada caso, genere una línea con un entero que represente el número de cadenas de longitud ~L~ que son casi palíndromos de grado ~K~ y constan solo de dígitos, modulado ~1000000007~ ~(10^9 + 7)~.

Ejemplo de Entrada

2
1 1
3 2

Ejemplo de Salida

10
100