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
sumantopal07: 2020-01-29 10:25:44

Please recommend questions similar to this

bmad_221: 2020-01-24 10:35:19

DP with Bitmasking will do:)

noob__coder: 2019-11-24 16:47:46

@nani_99...DCT would make the compile-time <.01 s....very bad question since brute force also give AC

nani_99: 2019-11-24 16:43:12

No, you are wrong @anonymous_09.You should use convolution

anonymous_09: 2019-11-16 21:38:27

(2^n)*n*c then fourier transformation gives AC in one go...!!!

ishancosmos25: 2019-10-11 16:02:19

Declared int instead of long long int, this will cause overflow . and lead to WA :)

agenta10: 2019-08-20 16:08:57

sometimes top down is better...(*..*)

anikett12: 2019-08-15 22:55:43

AC IN ONE GO...!!

pirate_joker1: 2019-08-15 16:16:48

TLE then i read comments
TLE then i carefully read comments about 1D dp
AC :)

Last edit: 2019-08-15 16:17:02
dmorgans: 2019-05-31 19:51:31

the top down approach gives TLE.... don't know why
bottom up - AC

Last edit: 2019-05-31 20:29:24

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