Prime Distance

You have an empty 1 × n grid. The cells of the grid are indexed from 1 to n from left to right. You have to put m identical coins in the grid. A cell can contain zero or more coins. If you pick a pair of cells each containing at least one coin, the distance between the cells must be a prime number. How many ways you can place the coins? As the number can be large, find answer modulo 109 + 7. Two ways are different if there is at least one cell which contains different number of coins. The distance between two cells indexed i, j is |i − j|.

Input

The first line contains T (1 ≤ T ≤ 2000) (the number of test cases). Each of the next T lines contains two integers n (1 ≤ n ≤ 105) and m (1 ≤ m ≤ 105) separated by a single space.

Output

For each case, print the case number and the answer modulo 109 + 7. Hint: In the first case, you can put both coins in cell 1, 2 or 3. Or you can put a coin in cell 1 and put another coin in cell 3. See picture. Note that in the 2nd case putting 3 coins in cell 1, 3, 5, is not valid, because the distance between cell 5 and cell 1 is a non-prime.

#13157Prime Distance

Input

Output