You are given an array $$A$$ consisting of $$N$$ non-negative integers. You are also given 2 integers $$p$$(a prime number) and $$k$$. You are required to count number of pairs $$(i, j)$$ where, $$1 \leq i < j \leq N$$ and satisying:

$$ (A_i^2 + A_j^2 + A_i*A_j) \text{ mod }p = k$$

where \(a \text{ mod } p = b\) means that \(b\) is the remainder when \(a\) is divided by \(p\). In particular, \(0 \leq b < p\).

You are given $$T$$ test cases.

Input format

The first line contains a single integer $$T$$ denoting the number of test cases.
For each test case:
- The first line contains three space-separated integers $$N$$, $$k$$, and $$p$$ denoting the length of the array, the required remainder/modulo, and the prime number respectively.
- The second line contains $$N$$ space-separated integers denoting the integer array $$A$$.

Output format

For each test case, print the number of pairs satisfying the equation in a separate line.

Constraints

$$ 1 \le T \le 1000 \\
1 \le N \le 5 \times 10^5 \\
1 \le p \le 10^9 \\
\text{p is prime} \\
0 \le k < p \\
0 \le A_i \le 10^9 \\
\text{Sum of N over all test cases does not exceed } 10^6 $$