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