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