Problem Statement

penguinman, the head of Penguin Academy, has decided to stock some bread for the students and sell it at the school store.

There are $N$ types of bread available, and penguinman will stock and sell exactly $K$ pieces of bread chosen from them. Any number of pieces of the same type may be stocked, and there may be types of which not even $1$ piece is stocked.

Before stocking, he surveyed the students and received $M$ responses. The $i\ (1\leq i\leq M)$-th response was the following.

• Please stock exactly $y_i$ pieces of the $x_i$-th type of bread.

penguinman wants to meet the students' requests as much as possible. Let $B_i$ be the number of pieces of the $i$-th type of bread stocked. By stocking the bread appropriately, minimize $\sum_{i=1}^{M} (B_{x_i}-y_i)^2$.

Since $B_i$ is a number of pieces of bread stocked, it must be a non-negative integer, and by the condition above, the sum of $B_i$ must be $K$. Under the constraints of this problem, the answer is at most $10^{18}$.

Answer $T$ test cases.

Input

Line $1$ of the input is as follows.

\(T\)

Then, $T$ test cases are given in order in the following format.

\(N\) \(M\) \(K\)
\(x_1\) \(y_1\)
\(x_2\) \(y_2\)
\(\vdots\)
\(x_M\) \(y_M\)

• $1\leq T\leq 100$
• $1\leq N,\ M\leq 2\times 10^5$
• $1\leq K\leq 10^9$
• $1\leq x_i\leq N$
• $1\leq y_i\leq 10^9$
• $M\times \max(K,\ \max(y))^2\leq 10^{18}$
• The sums of $N,\ M$ over all $T$ test cases each do not exceed $2\times 10^5$
• All inputs are integers

Output

Output over $T$ lines. On line $k$, print the minimum value of $\sum_{i=1}^{M} (B_{x_i}-y_i)^2$ for the $k$-th test case.

Sample

2
2 2 3
1 1
2 2
3 4 10
1 4
2 3
1 4
2 4

0
1

3
5 8 93
2 11
3 80
3 58
1 78
4 8
4 71
1 39
2 30
6 10 56
5 31
1 48
6 8
2 24
4 75
2 83
5 80
5 31
4 60
2 63
6 10 480
5 74
3 64
5 40
3 52
2 98
2 83
2 5
6 53
6 41
2 88

7659
17317
6216