import math
def isPrime(num):
    if(num==1):
        return False
    if(num==2):
        return True
    if(num%2==0):
        return False

    i = 3
    while(i<math.sqrt(num)+1):
        if num%i==0:
            return False
        i += 2
    return True

def main():
    n = int(input())
    ids = list(map(int, input().split()))

    print(len([i for i in ids if isPrime(i)]))


for _ in range(int(input())):
    main()