Maximizing Distinct Prime Numbers by Changing One Element

You are given an array of integers A = [a₁, a₂, …, aₙ]. You are allowed to change exactly one element of the array to any prime number. Your task is to maximize the number of distinct prime numbers present in the array after performing this change. Formally, if the original set of distinct prime numbers in the array is (P), then you may select one element aᵢ (if it is not already prime or even if it is, if beneficial) and change it to a prime number (p) such that the cardinality (|P \cup {p}|) is maximized. If no change can increase this number, the array remains unchanged.

Note: The input is read from standard input (stdin) and the output should be printed to standard output (stdout). All formulas are provided in LaTeX format as needed.

inputFormat

The first line contains a single integer T, representing the number of test cases. Each test case begins with an integer n, the number of elements in the array, followed by n space-separated integers representing the array elements. All input is provided via standard input (stdin).

outputFormat

For each test case, output a single line containing the maximum number of distinct prime numbers that can be obtained after modifying at most one element. The result for each test case should be printed on a new line in standard output (stdout).## sample

3
5 4 6 8 10 12
4 2 3 5 7
3 15 23 29

1
4
3