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
debsourav33: 2018-10-11 13:41:50

Learn Bitmask DP first.. Use mask to keep track which books have been taken so far.

elliot1: 2018-09-11 01:31:04

for those who solve the problem and come to show off in comments.. "fuck you"

souvikd_pro: 2018-08-19 03:56:20

After this, try: https://www.codechef.com/AUG14/problems/TSHIRTS

Last edit: 2018-08-19 03:59:23
be1035016: 2018-06-29 09:50:51

bitset tle:bitmask ac

s_a_k_s_h_a_m: 2018-06-14 22:22:48

question is quite easy
DP + bitmasking
use long long
for each test case dont clear complete dp table (I got 2 TLE)
10^8 memory can be used

ankit1cool: 2018-06-11 13:12:12

My first dp+bitmasking learnt a lot

horizon121: 2018-05-16 17:12:44

My first dp+bitmasking !! Very nice. Learnt alot

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


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