给定一张 $n$ 个点的有向图，点标号为 $1,2,\dots,n$，初始时对 $\forall i\in\{1,2,\dots,n-1\}$，从 $i$ 到 $i+1$ 有一条有向边。
你可以在其中再加入 $m$ 条有向边（起点终点任意），允许有重边和自环。
小 A 会从 $1$ 出发，以随机游走的形式行动，直到抵达 $n$。你希望最大化小A从 $1$ 移动到 $n$ 的期望步数。
定义随机游走是这样的一种移动方式：设小 A 当前在点 $x$，$x$ 有 $d$ 条出边，则小 A 会从这 $d$ 条出边中等概率随机选择一条走过去。
输入格式
从标准输入读入数据。
输入的第一行包含一个正整数 $T$，表示数据组数。
接下来 $T$ 行，每行包含三个整数 $n,m,p$，分别表示有向图的点数、你添加的边数以及答案的模数。
输出格式
输出到标准输出。
输出 $T$ 行，第 $i$ 行一个整数 $ans$ 表示第 $i$ 组数据中最大的期望步数对 $p$ 取模后的值（可以证明答案是有理数，设其用最简分数表示为 $\frac{a}{b}$，则你需要满足 $ans \cdot b \bmod p=a$，保证这样的 $ans$ 存在）。
样例数据
样例输入
4 3 2 97 10 25 233 6 12345 2333 1000000000 1000000000000000000 1000000007
样例输出
6 131 1206 161905971
数据范围与提示
| 测试包编号 | $n \le$ | $m \le$ | $T \le$ | 特殊性质 | 分数 |
|---|---|---|---|---|---|
| $1$ | $5$ | $5$ | $10$ | 无 | $10$ |
| $2$ | $10^{2}$ | $10$ | |||
| $3$ | $10^{8}$ | $10^{2}$ | $20$ | ||
| $4$ | $50$ | $3000$ | $3$ | $20$ | |
| $5$ | $10^{9}$ | $10^{9}$ | $10^{5}$ | $m\lt n-1$ | $10$ |
| $6$ | $10^{18}$ | 无 | 30 |
对于所有数据，保证 $T \le 10^5,1 \leq n \leq 10^9,0 \leq m \leq 10^{18},2\leq p\leq 10^9+7$ 且 $p$ 是质数。