#include<stdio.h>
#include<math.h>
#include<string.h>
typedef long long ll;
ll at[1000005];
ll prime(ll n)
{
	ll i,count=0;
	while(n%2==0)
	{
		count++;
		n=n/2;
	}
	if(count>at[2])
	at[2]=count;
	for(i=3;i<=sqrt(n);i=i+2)
	{
		count=0;
		while(n%i==0)
		{
			count++;
			n=n/i;
		}
		if(count>at[i])
		at[i]=count;
	}
	if(n>2)
	{
		if(at[n]==0)
		at[n]=1;
	}
}
int main()
{
	ll t,n,i,k,count;
	ll ar[100005];
	scanf("%lld",&t);
	while(t--)
	{
		for(i=0;i<1000005;i++)
		at[i]=0;
		count=0;
		scanf("%lld",&n);
		for(i=0;i<n;i++)
		scanf("%lld",&ar[i]);
		for(i=0;i<n;i++)
		prime(ar[i]);
		for(i=0;i<=1000005;i++)
		count=count+at[i];
	    printf("%lld\n",count);
	}
	return 0;
	
}