Problema B - Primómetro

O Dr. Bunsen Honeydew e o Beaker são dois cientistas muito especiais. Quase todas as suas invenções dão um resultado diferente do esperado, ficando o Beaker normalmente queimado ou eletrocutado. No entanto, conseguiram fazer funcionar algumas invenções muito importantes para toda a humanidade, como o detector de gorilas, o aquecedor de narizes ou um político robot!

Uma ideia nova surgiu agora na cabeça do Dr. Bunsen, não perdendo tempo em contá-la ao Beaker, que respondeu no seu jeito tradicional: "Mee-mee-mee mee!". A ideia foi tão fantástica que resolveram colocá-la logo em prática. Porque não fazer uma máquina que dado um número, indique de quantas maneiras diferentes esse mesmo número pode ser obtido como uma soma de números primos? Brilhante! Que invenção fantástica e útil para todos nós. O Dr. Bunsen resolvei chamá-la de primómetro.

Relembra que um primo é um número positivo maior que um que só é divisível por si próprio e por um. Por exemplo, o número 10, pode ser obtido como 2 diferentes somas de números primos:

        2 + 3 + 5 = 10
            3 + 7 = 10

Nota que a ordem onde aparecem os dígitos na soma é irrelevante, e por isso 3 + 7 é exactamente a mesma coisa que 7 + 3 e só deve ser contado uma vez. E nota também que na soma não podem aparecer números primos iguais (têm de ser todos diferentes).

Para abrilhantar ainda mais a máquina, e torná-la um sucesso comercial, o Dr. Bunsen resolveu ainda permitir que a máquina possa condicionar os primos a usar, obrigando-os a serem menores ou iguais a um determinado limite. Assim, por exemplo, se esse limite fosse 5, 10 passava apenas a ter 1 maneira de ser representando como uma soma de primos.

Não querendo perder esta oportunidade única, resolveste ajudar o Dr. Bunsen e o Beaker na sua tarefa!

O Problema

Escreve um programa que dado um número e um limite, calcula de quantas maneiras diferentes esse número pode ser representado como uma soma de números primos (diferentes entre si) menores ou iguais ao limite.

Input

Na primeira linha de input vem um número inteiro C indicando o número de casos a considerar (1 ≤ C ≤ 50)

Seguem-se exactamente C linhas, cada uma com dois números N e K representando respectivamente o número e o limite a considerar (1 ≤ N,K ≤ 3000).

Output

O output é constituído por C linhas, uma para cada caso de input.

Cada linha deve conter um único número, representando o correspondente número de maneiras diferentes de obter o número N através de uma soma de números primos menores ou iguais a K.

Nota que uma soma pode ser constituída por apenas um único número, ou seja, 5 pode ser representado de duas maneiras como soma de primos: 2+3 ou o próprio 5. E nota também que na soma, o mesmo número primo só pode aparecer uma única vez.

Exemplo de Input

6
10 10
10 5
5 5
8 30
4 4
18 50

Exemplo de Output

2
1
2
1
0
4