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 satisfies 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).