Soda has a complete undirected graph with $n$ vertices. He wants to color the edges with $m$ different colors conveniently labeled from $1$ to $m$. He first selects $p$ edges and colors them. Then he will randomly color the rest edges. He wants to know the total number of different good triangles among all possible graphs.
Let $i, j, k$ $(i < j < k)$ be three vertices in the graph. If there's an edge between $i$ and $j$, an edge between $j$ and $k$, an edge between $k$ and $i$. Then we call the tuple $(i, j, k)$ $(i < j < k)$ is a triangle in the graph. Let the colors for edge $(i,j)$, $(j,k)$, $(k,j)$ be $x$, $y$ and $z$. If $x \ne y$ and $x \ne z$ and $y \ne z$, then we call the triangle good.
Two triangles are considered different if at least one of the six numbers $(i, j, k, x, y, z)$ is different.
Input
There are multiple test cases. The first line of input contains an integer $T$ $(1 \le T \le 100)$, indicating the number of test cases. For each test case:
The first line contains three integers $n$, $m$ and $p$, $(3 \le n \le 100000, 1 \le m, p \le 200000)$.
Each of the next $p$ lines contains three integer $u, v, c$ $(1 \le u < v \le n, 1 \le c \le m)$ which means the edge $(u, v)$ is colored with color $c$.
Each edge will be given at most once. Most cases are small.
Output
For each test case, output the total number of good triangles modulo $2^{32}$.
