Problem Description
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≠y and x≠z and y≠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≤T≤100), indicating the number of test cases. For each test case:
The first line contains three integers n, m and p, (3≤n≤100000,1≤m,p≤200000).
Each of the next p lines contains three integer u,v,c (1≤u<v≤n,1≤c≤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 232.
Sample Input
1
4 6 6
1 2 1
1 3 2
1 4 3
2 3 4
2 4 5
3 4 6
Sample Output
4
