Given a directed graph with $n$ vertices labeled $1, 2, \dots, n$, there is initially a directed edge from $i$ to $i+1$ for all $i \in \{1, 2, \dots, n-1\}$.

You can add $m$ additional directed edges to the graph (with arbitrary start and end points), allowing for multiple edges and self-loops.

Little A starts at vertex $1$ and moves in a random walk until reaching vertex $n$. You want to maximize the expected number of steps for Little A to move from $1$ to $n$.

A random walk is defined as follows: if Little A is currently at vertex $x$ and there are $d$ outgoing edges from $x$, Little A will choose one of these $d$ edges with equal probability and move along it.

Input

The input is read from standard input.

The first line contains a positive integer $T$, representing the number of test cases.

Each of the next $T$ lines contains three integers $n, m, p$, representing the number of vertices in the directed graph, the number of edges you can add, and the modulus for the answer, respectively.

Output

Output to standard output.

Output $T$ lines, where the $i$-th line contains an integer $ans$ representing the maximum expected number of steps for the $i$-th test case modulo $p$. (It can be proven that the answer is a rational number; if it is represented as an irreducible fraction $\frac{a}{b}$, you need to satisfy $ans \cdot b \equiv a \pmod p$. It is guaranteed that such an $ans$ exists.)

Examples

Input 1

4
3 2 97
10 25 233
6 12345 2333
1000000000 1000000000000000000 1000000007

Output 1

6
131
1206
161905971

Constraints

For all data, it is guaranteed that $T \le 10^5, 1 \le n \le 10^9, 0 \le m \le 10^{18}, 2 \le p \le 10^9+7$, and $p$ is a prime number.