In every city of Triangle Country, all the enclosed blocks of streets are equilateral triangles with same area. In one of the city X, there is a main street across the city. Everyday Shik takes a walk starting from his home (located somewhere on the main street), and walking through n segment of streets. As usual, Shik feels somewhat puzzled and gets lost again. Therefore, he wishes back to the main street after he walks through n segment of streets. Please help Shik to calculate how many available routes that he can choose.
First line contains an integer T(1<=T<=100) indicating the number of test cases.
For each test case, there are an integer n (1<=n<=106) indicating the number of segments Shik will walk through and a prime number m (2<=m<=2*109).
For each test case, please output the number of available routes modulo m.
3 1 11 2 2 3 3
2 0 2
Migrated from old NTUJ.
Shik and Tmt
| No. | Testdata Range | Score |
|---|