Sphere Online Judge



SPOJ Problem Set (classical)

423. Assignments

Problem code: ASSIGN

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


Added by:Pawel Gawrychowski
Date:2005-10-08
Time limit:2.997s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel Pentium G860 3GHz)
Languages:All except: NODEJS PERL 6

hide comments
2014-08-16 09:27:00 Archit Jain
enjoyed solving it
There is no test case in which a student dislikes all the subjects
2014-04-17 19:58:30 saravanan
suppose if the input is
2
01
00

then what is the output?
- Should i take that second students cannot be assigned any as he doesnt like any ( so that the output is 0)
- or should i take that the second student can take any( so that the output is 1)
2014-03-02 17:42:27 Guilherme Sena
was getting WA because I used the "I64d" specifier for long long int. Watch out guys!
2013-02-04 11:17:56 foram


Last edit: 2013-05-20 04:25:11
2013-01-13 08:11:11 thefourtheye
Can anyone please explain the sample input and output, atleast the first one?
2011-06-14 08:17:55 alexandre
OMG it works!!! AC!!!
2011-06-14 08:14:39 gskhirtladze
Yes of course!
2010-04-30 12:57:25 Mudit Jain
if a student likes no subject? that means if all preferences are 0's then?
2009-11-25 08:14:51 Tom Chen
It does...but so slow
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.