Longest Increasing Prime Subsequence

Given a sequence of integers, your task is to find the length of the longest subsequence that is strictly increasing and consists only of prime numbers.

A number \(p\) is prime if it is greater than 1 and has no divisors other than 1 and itself, i.e., for every integer \(d\) with \(2 \leq d \leq \sqrt{p}\), \(p\) is not divisible by \(d\).

The subsequence must maintain the order of the original sequence. For example, if the sequence is [2, 4, 6, 3, 5, 7, 11, 13], the subsequence [2, 3, 5, 7, 11, 13] is strictly increasing and all elements are prime, so the answer is 6.

inputFormat

The first line of input contains an integer \(T\) representing the number of test cases.

Each test case begins with an integer \(N\) indicating the number of elements in the sequence, followed by \(N\) space-separated integers.

Input is provided via standard input.

outputFormat

For each test case, output a single line containing the length of the longest strictly increasing subsequence that consists only of prime numbers.

Output is printed to standard output.

## sample

3
6
2 3 5 7 11 13
5
1 4 6 8 10
8
2 4 6 3 5 7 11 13

6
0
6

</p>