Experiment "X": Explosions Expected

Time Limit: 10 Seconds    Memory Limit: 32768 KB

Unlucky scientist Vasya was tired of permanent mockeries of his colleagues. He built a time machine to go away into the future. But his machine had taken him into the past and then exploded!

Vasya needed some way to earn money! He has taken the job of the Court Alchemist of King Arthur. His first task is to create the philosophers' stone. Vasya has found $K$ ingredients and now conducts experiments which consist in mixing these ingredients in various proportions. More formally, each experiment consists in taking a1 ounces of the first ingredient, a2 ounces of the second and so on. Then all the ingredients are put into the crucible, carefully mixed and heated. All ai are non-negative integers, and their sum does not exceed S - the capacity of the crucible. In all Vasya's experiments at least two ingredients are taken, i.e. there are at least two ai greater than zero.

But all his experiments have been unsuccessful up to now. All mixtures have exploded! The King is unpleased. Maids of honour complain to Queen Guinevere about these awful explosion sounds! The King has decided to give one last chance to Vasya. Tomorrow Vasya is to conduct his next experiment, which could become the last. If the mixture explodes again, Vasya will be executed.

Fortunately, Vasya has just found a way to discard some definitely unsuccessful experiments. He has noted that if for some experiment plan (a1, a2, ..., aK) the mixture has exploded, it would explode for any plan (b1, b2, ..., bK) such that bi >= ai for all i. Now Vasya wants to count the number of possible experiments which are not definitely unsuccessful according to his unfortunate experience. He has taken out his pocket computer and now he is writing a program which will compute this number. Can you do this?

Input

The first line of input contains three positive integers 2 <= K <= 30, 2 <= S <= 10000, 0 <= M <= 20 where M is the number of experiments Vasya has already conducted. The next M lines contain K numbers each, one line per experiment.

Output

Output the number of possible experiment plans for which it is not evident that the mixture would explode.

This problem contains multiple test cases!

The first line of a multiple input is an integer N, then a blank line followed by N input blocks. Each input block is in the format indicated in the problem description. There is a blank line between input blocks.

The output format consists of N output blocks. There is a blank line between output blocks.

Sample Input

1

2 4 2
1 3
2 1

Sample Output

2

Submit

Source: Northeastern Europe 2003, Northern Subregion