SHOPPERS - SHOPPERS

A group of N shoppers go to a supermarket. The supermarket has M items. Each shopper wants to buy only the items he likes.

They plan to buy K items in all. A shopper can buy at max only one item. Some shoppers may not buy anything and some items might not be bought.

Input

First line contains the number of test cases.

Each test case contains three integers N, M and K separated by spaces. Then follow N lines containing M characters each.

If jth character of ith line is 1 then ith shopper likes item j.

1<= K <= N, M <= 13

Output

For each test case, output the number of ways K items in all can be bought.

Example

Input:
1
4 4 2
1111
0100
0100
1100

Output:
14

Added by:P != NP
Date:2010-10-22
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:C C++ 4.3.2 CPP CPP14 C99 JAVA PYTHON
Resource:MNNIT IOPC 2010

hide comments
2016-12-19 00:19:40
adding "if(k>m||k>n) while(1);" into AC solution gives TLE -> K<=N,M doesn't hold. Got lots of RE due to that.
2012-02-05 07:05:40 Allada Revanth Kumar
can two shoppers buy the same item ??
2011-02-15 18:17:41 Karl-Aksel Puulmann
No need for language limitations.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.