Vượt Ngục

Trong một buổi tìm hiểu về hệ thống an ninh nhà tù, FullHouse Dev được mời làm cố vấn công nghệ. Họ được giao nhiệm vụ phân tích các lộ trình có thể trong một kịch bản vượt ngục giả định để kiểm tra độ an toàn của nhà tù. Với kinh nghiệm trong lĩnh vực an ninh, FullHouse Dev bắt đầu nghiên cứu bài toán này.

Bài toán

Nhà tù có dạng ma trận \(N \times N\). Một số ô trong nhà tù được lắp đặt cảm biến chuyển động. Người tù bắt đầu từ ô \((1,1)\) và cần thoát ra ở ô \((N,N)\). Từ một ô hiện tại \((i,j)\), người tù có thể di chuyển đến các ô \((i-1,j)\), \((i+1,j)\), \((i,j-1)\), \((i,j+1)\) nếu các ô đó nằm trong ma trận và không có cảm biến. Nếu ô đầu tiên \((1,1)\) hoặc ô cuối cùng \((N,N)\) có cảm biến, việc vượt ngục là không thể thực hiện được.

INPUT FORMAT:

• Dòng đầu tiên chứa số nguyên \(T\) - số lượng test case
• Với mỗi test case:
  • Dòng đầu chứa số nguyên \(N\) - kích thước ma trận
  • \(N\) dòng tiếp theo, mỗi dòng chứa \(N\) số (0 hoặc 1), trong đó 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ù

Ràng buộc:

• \(1 \leq T \leq 100\)
• \(2 \leq N \leq 10^2\)

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

• Ở test case đầu tiên, có 2 đường đi khả thi để thoát khỏi nhà tù
• Ở test case thứ hai, có 4 đường đi khả thi
• Ở test case thứ ba, có 4 đường đi khả thi