The VIP Network

Input

The first line contains an integer $t$ (1 \le t \le 10^4) — the number of test cases.

The first line of each test case contains three integers $n$, $m$, and $k$ (1 \le k \le n \le 2 \cdot 10^5, 0 \le m \le \min\left(5 \cdot 10^5, \frac{n(n-1)}{2}\right)) — the number of cities, roads, and cities to upgrade to "VIP" status.

The following $m$ lines describe the roads. Each line contains two integers $u$ and $v$ (1 \le u, v \le n, u \ne v) denoting a bidirectional road between city $u$ and city $v$.

The graph contains no self-loops or multiple edges.

It is guaranteed that the sum of $n$ over all test cases does not exceed 2 \cdot 10^5, and the sum of $m$ over all test cases does not exceed 5 \cdot 10^5.

Output

For each test case, output a single integer — the minimum possible total congestion score of the road network after Fady optimally upgrades exactly $k$ cities to "VIP" status.

Examples

Note

In the first sample, the optimal choice is to upgrade city $1$ to "VIP" status. The congestion scores for the roads $(1,2)$, $(2,3)$, $(3,4)$, and $(4,1)$ become $2$, $3$, $3$, and $2$, respectively. The minimum total congestion score is 2 + 3 + 3 + 2 = 10.

Scoring

• Subtask $1$ ($50$ points): \sum n \le 20.

• Subtask $2$ ($250$ points): No additional constraints.