ASSIGN - Assignments


Problem

Your task will be to calculate number of different assignments of n different topics to n students such that everybody gets exactly one topic he likes.

Input

First line of input contains number of test cases c (1<=c<=80). Each test case begins with number of students n (1<=n<=20). Each of the next n lines contains n integers describing preferences of one student. 1 at the ith position means that this student likes ith topic, 0 means that he definitely doesn't want to take it.

Output

For each test case output number of different assignments (it will fit in a signed 64-bit integer).

Example

Input:
3
3
1 1 1
1 1 1
1 1 1
11
1 0 0 1 0 0 0 0 0 1 1 
1 1 1 1 1 0 1 0 1 0 0 
1 0 0 1 0 0 1 1 0 1 0 
1 0 1 1 1 0 1 1 0 1 1 
0 1 1 1 0 1 0 0 1 1 1 
1 1 1 0 0 1 0 0 0 0 0 
0 0 0 0 1 0 1 0 0 0 1 
1 0 1 1 0 0 0 0 0 0 1 
0 0 1 0 1 1 0 0 0 1 1 
1 1 1 0 0 0 1 0 1 0 1 
1 0 0 0 1 1 1 1 0 0 0 
11
0 1 1 1 0 1 0 0 0 1 0 
0 0 1 1 1 1 1 1 1 1 1 
1 1 0 1 0 0 0 0 0 1 0 
0 1 0 1 0 1 0 1 0 1 1 
1 0 0 1 0 0 0 0 1 0 1 
0 0 1 0 1 1 0 0 0 0 1 
1 0 1 0 1 1 1 0 1 1 0 
1 0 1 1 0 1 1 0 0 1 0 
0 0 1 1 0 1 1 1 1 1 1 
0 1 0 0 0 0 0 0 0 1 1 
0 1 1 0 0 0 0 0 1 0 1 

Output:
6
7588
7426


hide comments
vaibhavi760: 2016-06-23 06:12:28

took 1 day to solve and finally success nice question to understand bitmasking

Last edit: 2016-06-25 18:01:55
vijay kumar paliwal: 2016-06-02 07:48:19

Here comes my third fifty!! :)

ajay_5097: 2016-05-25 12:05:12

Question is worth trying !!

try2catch: 2016-01-22 07:03:39

I'm not getting the question. Can some1 explain test cases?

:.Mohib.:: 2015-11-18 22:06:15

top-down :D ;)

theweblover007: 2015-11-09 08:12:49

After juggling with TLE's for 4 hrs, Attained the enlightenment.

Last edit: 2015-11-09 10:22:28
rahul nagurtha: 2015-10-02 12:34:09

Can someone tell me why am i getting wrong answer instead of TLE ?

Abhilash: 2015-09-24 14:09:33

Topdown gets AC with few optimizations in code.

anando_du: 2015-08-31 16:22:18

Top DOwn ... single submission . AC . DP state is important here ....

Abhinandan Agarwal: 2015-08-30 15:46:20

A good problem indeed! Top down -TLE,
Bottom Up - AC


Added by:gawry
Date:2005-10-08
Time limit:2.997s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6 VB.NET