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 points 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:

• B is not on any (coordinate) axis.
• For each 1 ≤ i ≤ M, there exist j, 1 ≤ j ≤ k, such that b_j < a_ij.
• For each 1 ≤ j ≤ k, b_j is a non-negative integer.
• The sum of b_j doesn't exceed S.

Example

Input:
1
2 4 2
1 3
2 1

Output:
2

Hint

The two points are (1, 1) and (1, 2).