Một lớp học có \(n\) học sinh, cô giáo phân công cho học sinh trong lớp nghiên cứu \(n\) chủ đề học tập. Mỗi học sinh có sở thích học tập khác nhau, và không có học sinh nào muốn mình phải học một chủ đề không yêu thích.

Yêu cầu

• Đếm số cách phân chia \(n\) chủ đề học tập cho \(n\) học sinh (mỗi học sinh một chủ đề), sao cho mỗi học sinh đều được học đúng chủ đề mình yêu thích?

Input

• Dòng đầu tiên chứa số nguyên dương \(t\) - số lượng test cases.
• Trên \(t\) nhóm dòng tiếp theo, mỗi nhóm dòng mô tả một test case có cấu trúc:
  • Dòng đầu tiên chứa số nguyên dương \(n\).
  • Trên \(n\) dòng tiếp theo, mỗi dòng chứa \(n\) số nguyên \(a_{i,j}\), mô tả sở thích của học sinh thứ \(i\): Nếu \(a_{i,j}=0\) nghĩa là học sinh thứ \(i\) không thích chủ đề \(j\), ngược lại \(a_{i,j}=1\) nghĩa là học sinh thứ \(i\) yêu thích chủ đề \(j\).

Output

• In ra số cách phân chia thỏa mãn. Đáp án đảm bảo là một số nguyên \(64\) bit.

Ràng buộc

• \(1 \le t \le 80\)
• \(1 \le n \le 20\)

Input 1

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 1

6
7588
7426