Problem Description

The Floppy Cube is essentially a $1 \times 3 \times 3$ Rubik’s Cube. It is made up of 9 identical cubic pieces arranged into a $1 \times 3 \times 3$ cuboid. The puzzle consists of 4 corner pieces, 4 edge pieces and 1 centre piece. Each corner piece has four colours each, each edge piece has three colours each, while the centre piece has two colours (on the opposite faces). The puzzle can be thought of as twisting around its edge pieces. Each twist causes one edge piece to rotate 180 degrees in place, and the two adjacent corner pieces to swap position (while also being rotated). Of course, rotating or flipping the entire Floppy Cube are available moves as well. The purpose of the puzzle is to restore it to the state of having one colour per face.

Suppose that we wish to apply new colour stickers to a Floppy Cube in a colouring which is not necessary to be a standard colouring. Specifically, we have $n$ different colours available (with an unlimited supply of stickers of each colour), and we place one sticker on each of the 30 faces in any arrangement that we please. We are not required to use all the colours, and if desired the same colour may appear in more than one face of a single cubic piece.

We say that two such colouring $c_1$ and $c_2$ are essentially distinct if a cube coloured according to $c_1$ cannot be made to match a cube coloured according to $c_2$ by performing mechanically possible Floppy Cube moves. How many essentially distinct colourings are there with $n$ different colours available?

Input Format

The input has several test cases, and the first line contains an integer $T$ ($1 \le T \le 22222$) which is the total number of test cases. For each case, a line contains two integers $n$ and $P$ where $1 \le n, P \le 111111111$.

Output Format

For each case, calculate the number of distinct colouring with $n$ different colours available, and output the remainder when it divided by $P$.

3
1 32145
2 32145
3 32145

1
6738
30690