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
hello_world123: 2018-04-15 08:36:45

Why is time complexity O(n*2^n) and not O(n*n*2^n) ?

Aditya Kumar: 2018-04-12 20:54:51

bitmasking is cool!!

sinersnvrsleep: 2018-03-18 11:40:47

use long long int costed me a wrong answer

kkrishnaai: 2018-02-26 08:29:59

My 50th :)

amitboss: 2018-02-08 16:43:55

my first bitmasking and dp..
ac in 3 go!
Tle_>Tle->Ac!

excel_blaze: 2018-01-02 09:41:25

AC in 1 go.nice one to try bitmasking

kspoj: 2017-12-08 10:40:10

my first bitmasking + dp prob :D :D

grextrex: 2017-10-12 07:41:22

solved in one go... easy peasy

rohit1507: 2017-10-06 23:04:36

Just Wow! Test cases can be improved!

beginner5022: 2017-09-28 13:43:48

Last edit: 2017-09-28 14:34:42

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