Nefertiti foi rainha do Egito, esposa de Akhenaton, e é tida como uma das mais belas mulheres da história do mundo. Seu busto, que pode ser visto no Altes Museum em Berlim, Alemanha, comprova sua beleza rara. O escultor inclusive não terminou a obra, deixando de incrustar a córnea no olho direito, para evitar a ira dos deuses. A vida familiar da rainha do Egito obrigava-a a cuidar de diversas coisas, inclusive do cardápio da corte. Akhenaton era conhecido por detestar que a comida se repetisse com frequência, e mesmo em intervalos regulares. Ele desejava que os cardápios não apenas fossem diferentes, como fosse praticamente impossível descobrir quando um prato se repetiria. Isso criou um enorme problema para os cozinheiros do rei, que não apenas tinham de elaborar os diferentes pratos como planejar a ordem em que deveriam ser oferecidos. Nefertiti teve, então, uma ideia. Elaborou uma lista de N pratos, que seriam repetidos. Uma exigência dela era que a diferença entre o prato preparado no i-ésimo dia e i fosse, em módulo, menor que um certo k dado. Tal exigência, além de ser por motivos religiosos, em virtude de obrigações dos egípcios a Ra, se devia também ao fato de que os ingredientes do prato eram conseguidos neste intervalo, e também estavam sujeitos a perder a validade para o consumo. Sua tarefa neste programa é determinar, dado um inteiro N (número de diferentes pratos) e um inteiro K, quantos diferentes planejamentos podemos fazer (que são, na verdade, permutações π de {1,2,...,n}) que satisfazem a restrição abaixo:

|π(i) - i| ≤ K, para i = 1,...,N.

Entrada

A entrada é composta por diversas instâncias. A primeira linha da entrada contém um inteiro T indicando o número de instâncias.
A primeira (e única) linha de cada instância contém dois inteiro N e K, onde 1 ≤ N ≤ 100 e 1 ≤ K ≤ 6.

Saída

Para cada instância imprima uma linha contendo o número de planejamentos diferentes.

Exemplo

Entrada:
4
3 1
3 2
10 3
100 1

Saída:
3
6
19708
573147844013817084101