Nhân ngày lễ tình yêu 14/03 là ngày mà con trai tặng quà cho người con gái mình thương. Để đáp lại tình cảm và món quà mà người yêu đã tặng mình ngày 14/02, Cường nghĩ phải mua một món quà thật đặc biệt, chứ không phải đơn thuần là kẹo socola như mọi người.

Cường đi dạo qua một vòng \(ICTU\) và thấy một quán bán đồ lưu niệm thật đẹp. Đặc biệt là chiếc vòng tay với các hạt trong suốt gắn các con số mà khách hàng có thể tự chọn những con số đó. Nghĩ bụng đúng là món quà vừa ý người yêu vì người yêu Cường rất thích toán và các con số. Cường quyết định chọn một chiếc vòng đặt biệt và có đầy tính toán học.

Chiếc vòng tay gồm \(n\) hạt trong suốt. Mỗi hạt chứa một số nguyên \(p\) và tổng hai số nguyên cạnh nhau tạo thành một số nguyên tố. Nhiệm vụ của bạn là với n hạt trong suốt chứa các số nguyên \(p\), hãy đưa ra tổng số cách xếp n hạt đó vào chiếc vòng tay thoả mãn yêu cầu trên.

Đầu vào:

• Dòng đầu tiên chứa số \(T\) là số test. \((1 \leq T \leq 100)\).
• Mỗi test chứa 2 dòng
  • Dòng thứ nhất chứa số \(n\) là số lượng phẩn tử cần xếp \((3 \leq n \leq 16)\).
  • Dòng thứ hai chứa n số \(p\) là dãy số nguyên cần xếp \((1 \leq p \leq 50)\). Mỗi số cách nhau một dấu cách.

Đầu ra: Với mỗi test in ra trên một dòng chứa số nguyên duy nhất là tổng số cách sắp xếp thoả mãn bài toán.

Input

2
8
1 2 3 4 5 6 7 8
6
1 2 3 4 5 6

Output

4
2

Giải thích:

Với test thứ 2 gồm 6 số từ 1 tới 6. Ta có 2 cách sắp xếp là: 1-4-3-2-5-6 và 1-6-5-2-3-4