Put a Point in a Hyperspace
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 aij(1<=i<=M, 1<=j<=K), which shows that there is one point (ai1, ai2, ... aik) 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(b1, b2, ... bk) in the hyperspace satiesfied the following constraints:
- B is not on any (coordinate) axis.
- For each 1<= i <= M, there exist j, 1<=j<=k, such that bj < aij.
- For each 1<=j<=k, bj is a non-negative integer.
- The sum of bj doesn't exceed S.
Example
Input: 1 2 4 2 1 3 2 1Output: 2
Hint
The two points are (1,1) and (1,2).