Vượt Ngục 2

Trong một buổi hẹn hò lãng mạn, FullHouse Dev đã kể cho người yêu nghe về một bài toán thú vị về tù nhân Alfie. Alfie, một người thông minh và mưu trí, đang tìm cách vượt ngục khỏi nhà tù huyền thoại. Sau nhiều ngày quan sát, anh ta phát hiện nhà tù có cấu trúc là một ma trận \(N \times N\). Một số ô trong nhà tù được lắp đặt cảm biến chuyển động. Alfie cần tính toán số lượng đường đi khác nhau để thoát khỏi nhà tù mà không chạm vào các cảm biến.

INPUT FORMAT:

• Dòng đầu tiên chứa số nguyên \(T\) - số lượng test case
• Dòng đầu tiên của mỗi test case chứa số nguyên \(N\) (kích thước ma trận \(N \times N\))
• \(N\) dòng tiếp theo, mỗi dòng chứa \(N\) số, mỗi số là 0 hoặc 1 (1 đại diện cho ô có cảm biến chuyển động)

OUTPUT FORMAT:

• Với mỗi test case, in ra số lượng đường đi khác nhau có thể để thoát khỏi nhà tù

Lưu ý:

• Alfie bắt đầu từ ô \((1,1)\) và cần đến ô \((N,N)\)
• Alfie có thể di chuyển theo 4 hướng: lên, xuống, trái, phải
• Nếu ô đầu tiên \((1,1)\) hoặc ô cuối cùng \((N,N)\) có cảm biến, Alfie không thể thoát được

Ví dụ

INPUT

3
4
0 1 1 0 
0 0 1 0 
0 0 0 0 
0 1 1 0 
4
0 0 0 1 
0 0 0 0 
1 1 1 0 
1 0 0 0 
4
0 1 1 0 
0 0 1 1 
0 0 0 0 
0 1 0 0

OUTPUT

2
4
4

Giải thích

• Trong test case đầu tiên, có 2 đường đi khả thi để Alfie thoát khỏi nhà tù mà không chạm vào cảm biến
• Trong test case thứ hai và ba, có 4 đường đi khả thi cho mỗi trường hợp

Ràng buộc:

• \(1 \leq T \leq 100\)
• \(2 \leq N \leq 10\)
• Ma trận chỉ chứa giá trị 0 và 1