Flauta india P86839

Walker no solo cultiva el cuerpo: también cultiva el espíritu. Para ello, nada mejor que relajarse tocando una melodía con su flauta india navaja. Esta flauta puede hacer sonar $n$ notas distintas (desde la nota $0$, hasta la nota $n-1$). Sin embargo, las reglas de composición melódica navajas son muy estrictas:

• La primera nota de la melodía debe ser la nota 0.

• La última nota de la melodía debe ser la nota $n-1$.

• Cada nota tiene que ser exactamente la misma, una nota más o una nota menos que la anterior.

• La misma nota no puede aparecer tres veces consecutivamente en la melodía.

Por ejemplo, las siguientes son melodías navajas de duración $k=7$ que pueden tocarse con una flauta india de $n=4$ notas:

0123233 $\qquad$ 0011233 $\qquad$ 0121123 $\qquad$ 0100123

Por contra, las siguientes melodías navajas no son válidas, puesto que incumplen los 4 principios anterioreS:

1233233 $\qquad$ 0123212 $\qquad$ 0013223 $\qquad$ 0122233

Se te pide que digas, dados los valores $n$ y $k$, el número de melodías navajas distintas que Walker podría interpretar.

Entrada

La entrada contiene el número $N$ de casos en una línea, seguido de $N$ líneas con los números $1\le n\le 20$ y $1\le k\le 30$ de cada caso.

Salida

Escribe, para cada caso, el número de melodías navajas distintas de $k$ notas de duración que es posible interpretar con una flauta india de $n$ notas. Tu programa tiene 1 segundo de CPU para resolver cada entrada.

Puntuación

• TestA:   Entradas con $N\le 20$, $n=1$ y $k\le 10$, como el Ejemplo 1.

• TestB:   Entradas con $N\le 20$, $n \le 2$ y $k\le 10$, como el Ejemplo 2.

• TestC:   Entradas con $N\le 20$, $n \le 4$ y $k\le 10$, como el Ejemplo 3.

• TestD:   Entradas con $N\le 20$, $n \le 8$ y $k\le 10$, como el Ejemplo 4.

• TestE:   Entradas con $N\le 100$, $n \le 10$ y $k\le 20$, como el Ejemplo 5.

• TestF:   Entradas con $N\le 100$, $n \le 20$ y $k\le 30$, como el Ejemplo 6.

• TestG:   Entradas con $N\le 10000$, $n \le 20$ y $k\le 30$.