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    0011233    0121123    0100123

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

1233233    0123212    0013223    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≤ n≤ 20 y 1≤ k≤ 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≤ 20, n=1 y k≤ 10, como el Ejemplo ‍1.  ‍15 Puntos ‍

• TestB:  ‍ Entradas con N≤ 20, n ≤ 2 y k≤ 10, como el Ejemplo ‍2.  ‍15 Puntos ‍

• TestC:  ‍ Entradas con N≤ 20, n ≤ 4 y k≤ 10, como el Ejemplo ‍3.  ‍15 Puntos ‍

• TestD:  ‍ Entradas con N≤ 20, n ≤ 8 y k≤ 10, como el Ejemplo ‍4.  ‍15 Puntos ‍

• TestE:  ‍ Entradas con N≤ 100, n ≤ 10 y k≤ 20, como el Ejemplo ‍5.  ‍15 Puntos ‍

• TestF:  ‍ Entradas con N≤ 100, n ≤ 20 y k≤ 30, como el Ejemplo ‍6.  ‍15 Puntos ‍

• TestG:  ‍ Entradas con N≤ 10000, n ≤ 20 y k≤ 30.  ‍10 Puntos ‍