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