Maximum Prime Piles

In this problem, you are given multiple test cases. For each test case, you will first receive an integer ( n ) denoting the number of piles, followed by ( n ) integers representing the number of items in each pile. Your task is to count how many piles have a prime number of items. A positive integer ( p ) is prime if and only if ( p > 1 ) and its only divisors are 1 and ( p ), i.e., [ p \text{ is prime if } p > 1 \text{ and } \nexists d \in \mathbb{Z} \text{ with } 1 < d < p \text{ such that } d \mid p. ] Print the count for each test case on a new line.

inputFormat

The first line of input contains a single integer ( T ) representing the number of test cases. Then for each test case, the first line contains an integer ( n ) — the number of piles. The next line contains ( n ) space-separated integers representing the elements of the piles.

outputFormat

For each test case, output a single integer which is the count of piles with a prime number of items. Each result should be printed on its own line.## sample

3
3
5 4 9
4
6 8 10 15
5
17 19 23 6 45

1
0
3