Your task will be to calculate number of different assignments of N different jobs to N workers such that everybody gets exactly one job he likes.
Input
First line of input contains number of test cases t. Each test case begins with number of workers n. Each of the next n lines contains n integers describing preferences of ith worker. 1 at the ith position means that this worker likes ith job, 0 means that he doesn't like it.
Output
For each test case output number of different assignments
Constraints:- t<=10,1<=n<=20;
Example
Input
1
3
1 1 1
1 1 1
1 1 1
Output
6
Explaination :- All the workers like every job so we can assign all the jobs in 6 possible ways.
Problem author:- Mohit jain