The Sell N' Profit shop has recently had a raffle contest with a prize of a dress and matching shoes to some of their regular customers. They have set aside an equal number of dresses and pairs of shoes of different designs for the purpose.
The plan was going quite well until one customer pointed out that not all the dresses and all the pairs of shoes match each other (i.e. you won't look good if you wore that dress and that pair of shoes at the same time - but the same dress or shoes might look good with something else). So, simply giving someone a dress and a pair of shoes at random, risks angering their customers. They have to give each winner a dress and shoes that match. But some pairs of (dress, shoes) are so adorable to girls such that if they are given to any girl, she would be happier than ever and she may become a great customer of the shop. These pairs are called super matching pairs. But, choosing such pair may lead to a situation that some other girls get non-matching (dress, shoes) pairs.
Now you are given n dresses and n pairs of shoes, a list of what dress matches which shoes and some super matching (dress, shoes) pairs. As the company have lack of fashion sense, they ask you to find how many ways there are to make up n sets of dresses and matching shoes, such that either all the girls are happy (got matching dress and shoes), or at least one of the girls got a super matching pair (in this case some girls may get non matching pairs).
Input
Input starts with an integer T (≤ 100), denoting the number of test cases.
Each case starts with an integer n (1 ≤ n ≤ 15) by itself on a line, denoting the number of dresses and pair of shoes. Each of the next n lines contains n space separated integers (one of 0, 1 or 2). The jth integer in ith line represents the status of the ith dress and jth pair of shoes. 0 means that ith dress doesn't match jth pair of shoes. 1 means they match. 2 means they are super matching.
Output
For each case, print the case number and number of ways you can form n sets of dresses and shoes.
Sample
| Sample Input | Sample Output |
|---|---|
2 3 0 1 1 1 1 0 1 0 1 3 1 1 2 2 1 0 1 1 2 | Case 1: 2 Case 2: 4 |