B. Poker Number
time limit per test
15 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The sum of the points of the remaining cards in a deck of playing cards after removing the jokers can be easily calculated as follows: $$$\dfrac{4 \times 13 \times (13+ 1)}{2} = 364$$$. We define numbers like $$$364$$$ as Poker Numbers, as they can be written as $$$K \cdot \dfrac{X(X+1)}{2}$$$ for some $$$K\ge 1, X \ge 2$$$.

Your task is to solve the following problem. Given $$$n, c, p$$$, compute:

$$$$$$ \left( \sum\limits_{u \in S_n}c^{u} \right) \bmod p $$$$$$

where $$$S_n$$$ denotes the set of Poker Numbers between $$$1$$$ and $$$n$$$.

Input

The first line contains an integer $$$T$$$ ($$$1\le T \le 20$$$), representing the number of test cases.

Each test case consists of a single line containing three integers $$$n,c,p$$$ ($$$1\le n \le 10^{10}$$$, $$$1 \le c \lt p \le 10^{9} + 7$$$). It is guaranteed that $$$p$$$ is a prime.

Output

For each test case, output the answer in a single line.

Example
Input
2
10 2 1000000007
20 2 1000000007
Output
1608
1349192
Note

For $$$n=10$$$, $$$S_{10}=\{3,6,9,10\}$$$, so for the first example, the answer is $$$2^3+2^6+2^9+2^{10}=1608$$$.