Suppose we have an *n-dimensional* supercomputer with an infinite number of processors. Every processor has a vector of integers as its (*n-dimensional*) coordinates and can be thought of as a point in the -dimensional space. Furthermore, at every -dimensional lattice point, there is a processor. Two processors are called *neighbors* if their coordinate vectors are different in only one position, and the absolute difference of the numbers in that position is equal to . For example and are neighbors, and so are and . But and , and and , are not neighbors.

Some processors of this computer are infected by a virus. At time , only one processor is infected. After every second, all uninfected processors that are neighbors with infected ones become infected too. Given and , calculate the number of processors that are infected after seconds, modulo .

**Input Format**

The first line contains an integer , the number of test cases.

Each of the next lines contains two integers and , separated by a space.

**Output Format**

For every test case, write the answer in a single line.

**Constraints**

The sum of all 's in one file does not exceed

**Sample Input**

```
5
2 0
2 1
2 2
3 1
1 10
```

**Sample Output**

```
1
5
13
7
21
```

**Explanation**