Count Prime Sum Pairs

Given multiple test cases, each test case consists of an integer N and a list of N integers. Your task is to count the number of distinct pairs (i, j) with i < j such that the sum nums[i] + nums[j] is a prime number. A pair is counted at most once even if the same prime sum is obtained from different pairs.

Formally, for each test case, let \( S = { nums[i] + nums[j] : 0 \le i < j < N } \). Count the number of elements in \( S \) that are prime. Recall that a prime number \( p \) is an integer greater than 1 that has no divisors other than 1 and \( p \) itself.

inputFormat

The input is read from standard input (stdin) and has the following format:

T
N_1
a_11 a_12 ... a_1N
N_2
a_21 a_22 ... a_2N
...
N_T
a_T1 a_T2 ... a_TN

Here, T is the number of test cases. For each test case, the first line contains an integer N (the number of elements in the list), followed by a line with N space-separated integers.

outputFormat

For each test case, output a single line to standard output (stdout) containing the count of distinct pairs whose sum is a prime number.

1
2
1 2

1