Problem Description

A plane partition is a two-dimensional array of nonnegative integers a_i,j (0<=i<n, 0<=j<m) that satisfies
1. 0<=a_i,j<=p
2. a_i,j>=a_i,j+1
3. a_i,j>=a_i+1,j

In this problem, we add some additional constrains in the following form:
Given x, y, z, there exists some integer k (may be negative) such that a_x+k,y+k=z+k.

Note: For i and j do not satisfy 0<=i<n and 0<=j<m, a_i,j does not exist.

Count how many valid plane partitions are there.

Input

First line, number of test cases, T.
Following are T test cases. For each test case, the first line contains four integers, n, m, p, t, where the last one is the number of additional constraints.
Following are t lines, each line contains three integers, x, y, z.

T<=200
1<=n,m,p<=7
0<=x,y,z<=7
It's possible that there is no valid plane partitions.

Output

T lines. Each line is answer to the corresponding test case.

2
1 1 1 0
1 1 1 1
1 1 1

2
1