Longest Prime Subsequence

You are given an array of integers. Your task is to find the length of the longest consecutive subsequence of prime numbers in the array. A prime number is a number \(n\) such that \(n > 1\) and its only divisors are 1 and \(n\) itself. For example, 2, 3, 5, and 7 are primes, while 1, 4, and 6 are not.

The input begins with an integer \(T\) representing the number of test cases. For each test case, the first integer is \(N\), the number of elements in the array, followed by a line containing \(N\) space-separated integers. For each test case, output the maximum length of a consecutive subsequence in which every number is prime.

Example: Consider the array [2, 6, 4, 7]. There is one prime (2) at the beginning and one at the end (7) but they are not consecutive. Thus, the answer is 1 because the longest block of adjacent primes has length 1.

inputFormat

The first line of input contains a single integer (T) denoting the number of test cases. For each test case:

• The first line contains an integer (N), the number of elements in the array.
• The second line contains (N) space-separated integers.

All input is read from standard input (stdin).

outputFormat

For each test case, output a single integer on a new line representing the length of the longest consecutive subsequence of prime numbers. Output the result to standard output (stdout).## sample

3
4
2 6 4 7
5
1 3 5 8 9
6
10 15 16 17 18 19

1
2
1