Mảng số nguyên tố

Trong một chuyến đi mua sắm tại trung tâm thương mại, FullHouse Dev tình cờ bắt gặp một câu đố thú vị được dán trên bảng thông báo. Họ quyết định cùng nhau giải quyết bài toán này trong lúc nghỉ giải lao.

Bài toán

FullHouse Dev được cung cấp một mảng có \(n\) số nguyên. Nhiệm vụ của họ là tìm số bộ ba chỉ số \(i\), \(j\), \(k\) thỏa mãn điều kiện \(A[i] + A[j] + A[k]\) là số nguyên tố.

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 tiên chứa một số nguyên \(n\)
  • Dòng thứ hai chứa \(n\) số nguyên \(A[i]\)

OUTPUT FORMAT:

• Với mỗi test case, in ra số lượng bộ ba thỏa mãn điều kiện đã cho trên một dòng riêng biệt

Ràng buộc:

• \(1 \leq T \leq 100\)
• \(1 \leq n \leq 1000\)
• \(1 \leq A[i] \leq 1000\)

Ví dụ

INPUT

2
4
4 5 6 2
4
1 1 4 5

OUTPUT

0
1

Giải thích

• Ở test case đầu tiên, không có bộ ba nào thỏa mãn điều kiện đã cho.
• Ở test case thứ hai, có một bộ ba thỏa mãn là \((1,1,5)\) vì \(1 + 1 + 5 = 7\) là số nguyên tố.