C. Elliptic-EX
time limit per test
7 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Given integers $$$A, B$$$ and a prime number $$$p$$$, count the number of integer pairs $$$(x,y)$$$ such that $$$0 \le x, y \lt p$$$, and $$$y^2 \equiv x^3+Ax+B \pmod p$$$.

Input

The first line contains an integer $$$t$$$ ($$$1\le t \le 10$$$), denoting the number of test cases. Then $$$t$$$ lines follow, each containing three integers $$$A, B, p$$$ ($$$0 \le A, B \lt p \lt 10^{18}$$$, $$$p$$$ is prime) describing a test case.

Output

For each test case, output the answer on one line.

Scoring
  • Subtask 1 (7 points): $$$p \lt 10^6$$$
  • Subtask 2 (22 points): $$$t = 1, p \lt 10^9$$$
  • Subtask 3 (71 points): No additional constraints
Examples
Input
3
1 4 7
4 3 5
2 2 17
Output
9
2
18
Input
1
308184258 715742567 725717821
Output
725703415
Input
1
249815569918219069 761790217620034868 821318760275393441
Output
821318761834519883