Recent excavations have discovered the rests of an extincted race of pseudo-human primates called Omgillas (not to mistake for gorillas). Among other curiosities, they eated raw fish, slept at least twelve hours a day, and shaved their heads twice a year.

On the other hand, they must knew some basic mathematics, since they used coins with prime values: 2, 3, 5, 7, 11, 13, 17, 19, 23 and 29. This strange choice (for instance, there was no way to buy something of value 1 without change) and the fact that Omgillas were a bit silly caused a lot of confusion and their eventual extintion.

The sistem of coins of Omgillas is original enough to be investigated. Unfortunately, current humans are not much more intelligent. Therefore, a program that helps with this task would be welcome. Take into account that the coins were quite big and heavy, so only a few could be used in each transaction. It is known that the strongest Omgilla, the mythical warrior Obok-Aman, was able to carry just 20 coins.

To sumarize:
Write a program such that, given a number of coins *c* and a value *v*,
prints the number of different ways to get an amount of *v*
with exactly *c* coins.
Assume an infinite suply of coins of every kind: 2, 3, 5, …, 29.

**Input**

Input begins with the number of cases *n*,
followed by *n* pairs of natural numbers *c* and *v*.
Assume 1 ≤ *c* ≤ 20 and 1 ≤ *v* ≤ 10^{6}.

**Output**

For every case,
print the number of different ways to get a value *v* with exactly *c* coins.

Public test cases

**Input**

2 3 11 10 100

**Output**

2 947

Information

- Author
- Salvador Roura
- Language
- English
- Official solutions
- C++
- User solutions
- C++
- Event
- Segon Concurs de Programació de la UPC - Segona Semifinal
- Date
- 2004-09-15