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 .
The first line contains an integer , the number of test cases.
Each of the next lines contains two integers and , separated by a space.
For every test case, write the answer in a single line.