407766: GYM102891 C Elliptic-EX

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

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 < p < 10^{18}$$$, $$$p$$$ is prime) describing a test case.

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

• Subtask 1 (7 points): $$$p < 10^6$$$
• Subtask 2 (22 points): $$$t = 1, p < 10^9$$$
• Subtask 3 (71 points): No additional constraints

3
1 4 7
4 3 5
2 2 17

9
2
18

1
308184258 715742567 725717821

725703415

1
249815569918219069 761790217620034868 821318760275393441

821318761834519883