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

见题面

见题面