Bamboo Pole-vault is a massively popular sport in Xzhiland. And Master Phi-shoe is a very popular coach for his success. He needs some bamboos for his students, so he asked his assistant Bi-Shoe to go to the market and buy them. Plenty of Bamboos of all possible integer lengths (yes!) are available in the market. According to Xzhila tradition,

Score of a bamboo = Φ (bamboo's length)

(Xzhilans are really fond of number theory). For your information, Φ (n) = numbers less than n which are relatively prime (having no common divisor other than 1) to n. So, score of a bamboo of length 9 is 6 as 1, 2, 4, 5, 7, 8 are relatively prime to 9.

The assistant Bi-shoe has to buy one bamboo for each student. As a twist, each pole-vault student of Phi-shoe has a lucky number. Bi-shoe wants to buy bamboos such that each of them gets a bamboo with a score greater than or equal to his/her lucky number. Bi-shoe wants to minimize the total amount of money spent for buying the bamboos. One unit of bamboo costs 1 Xukha. Help him.

Input

Input starts with an integer T (≤ 100), denoting the number of test cases.

Each case starts with a line containing an integer n (1 ≤ n ≤ 10000) denoting the number of students of Phi-shoe. The next line contains n space separated integers denoting the lucky numbers for the students. Each lucky number will lie in the range [1, 10⁶].

Output

For each case, print the case number and the minimum possible money spent for buying the bamboos. See the samples for details.

#include<stdio.h>

#include<algorithm>

#include<iostream>

#include<string.h>

#include<stdlib.h>

#include<math.h>

#include<map>

#include<set>

using namespace std;

bool prime[3300000+5];

int su[300000];

typedef long long LL;

typedef struct pp

{

        int x;

        int id;

} ss;

ss ola[3300000+5];

int aa[10005];

bool cmp(struct pp nn,struct pp mm)

{

        if(nn.x==mm.x)

                return nn.id<mm.id;

        else return nn.x<mm.x;

}

typedef unsigned long long  ll;

int main(void)

{

        int i,j,k;

        for(i=2; i<=7000; i++)

        {

                if(!prime[i])

                        for(j=i; i*j<=(3300000); j++)

                        {

                                prime[i*j]=true;

                        }

        }

        int ans=0;

        for(i=2; i<=(3300000); i++)

                if(!prime[i])

                        su[ans++]=i;

        for(i=1; i<=3300000; i++)

        {

                ola[i].id=i;

                ola[i].x=i;

        }

        for(i=0; i<ans; i++)

        {

                for(j=1; su[i]*j<=3300000; j++)

                {

                        ola[su[i]*j].x=ola[su[i]*j].x/(su[i])*(su[i]-1);

                }

        }

        for(i=2; i<3300000; i++)

        {

                if(ola[i].x>ola[i+1].x)

                {

                        ola[i+1].x=ola[i].x;

                }

        }

        scanf("%d",&k);

        int s;

        int p,q;

        for(s=1; s<=k; s++)

        {

                LL sum=0;

                scanf("%d",&p);

                for(i=0; i<p; i++)

                {

                        scanf("%d",&aa[i]);

                        int l=2;

                        int r=4*1000000;

                        int zz=0;

                        while(l<=r)

                        {

                                int mid=(l+r)>>1;

                                if(ola[mid].x<aa[i])

                                {

                                        l=mid+1;

                                }

                                else

                                {

                                        zz=mid;

                                        r=mid-1;

                                }

                        }

                        sum+=ola[zz].id;

                }

                printf("Case %d: %lld Xukha\n",s,sum);

        }

        return 0;

}