Input

Multiple test cases, the number of them is given in the very first line.

For each test case:

The first line contains 3 space-separated integers K(2<=K<=30), S(2<=S<=10000), M(0<=M<=20). M lines follow, each contains K non-negative integers a_ij(1<=i<=M, 1<=j<=K), which shows that there is one point (a_i1, a_i2, ... a_ik) in the K-D hyperspace. No two point will be the same, and none of them lies on any (coordinate) axis.

Output

For each test case:

Output a single integer which shows the number of the points B(b₁, b₂, ... b_k) in the hyperspace satiesfied the following constraints:

Example

Input:
1
2 4 2
1 3
2 1
Output:
2
Hint
The two points are (1,1) and (1,2).