Euler's phi function for a positive integer N is usually denoted as φ(N) and defined as the number of positive integers less than or equal to N that are coprime with N.

DA-IICT is organising its sports event in the month of October and this time they have introduced a new game called climbing ladder.

The game is as follows:
Each player is given a ladder of height h and the score of that person is given by φ(h). 

The cost of a ladder is same as its height. Since each player has practised a lot this time and each player knows the maximum score they can achieve, as a manager of the event you need to find the minimum amount of money required to bring the ladders so that each player gets a ladder with a score equal to or greater than his maximum score. 

Input Format:-

First line contains t - number of test cases.

Each case starts with a line containing an integer n, the number of participants. The next line contains n space separated integers denoting the maximum achievable score of the participant.

Output Format:-

For each case, print the minimum possible money spent for buying the ladders.

Constraints:-

1 ≤ t ≤ 100

1 ≤ n ≤ 10000

1 ≤ Score s ≤ 1000000

Author :- Nikhil Tekwani

SAMPLE INPUT
2
4
1 2 3 4
2
1 1

SAMPLE OUTPUT
14
2

Explanation

For the first test case, 
score 1 -> cost = 1
score 2 -> cost = 3
score 3 -> cost = 5
score 4 -> cost = 5
Total  = 14
from bisect import bisect_left

primes = []

def get_primes(n):
    
    sieve = [True] * (n/2)

    for i in xrange(3,int(n**0.5)+1,2):
        if sieve[i/2]:
            sieve[i*i/2::i] = [False] * ((n-i*i-1)/(2*i)+1)
    
    return [1] + [2*i for i in xrange(1,n/2) if sieve[i]]
	

primes = get_primes(1000100)

for _ in xrange(input()):
	n = int(raw_input())
	print sum(map(lambda x:1 if bisect_left(primes, int(x)) < 1 else primes[bisect_left(primes, int(x))]+1, raw_input().split()))