PUTIN - 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 satisfies 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 1

Output:
2
Hint

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


Added by:Fudan University Problem Setters
Date:2008-04-19
Time limit:10s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: C99 ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:ACM/ICPC NEERC Northern Subregion Contest 2003; description by Blue Mary

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.