#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;
}
I2luY2x1ZGU8c3RkaW8uaD4KI2luY2x1ZGU8bWF0aC5oPgojaW5jbHVkZTxzdHJpbmcuaD4KdHlwZWRlZiBsb25nIGxvbmcgbGw7CmxsIGF0WzEwMDAwMDVdOwpsbCBwcmltZShsbCBuKQp7CglsbCBpLGNvdW50PTA7Cgl3aGlsZShuJTI9PTApCgl7CgkJY291bnQrKzsKCQluPW4vMjsKCX0KCWlmKGNvdW50PmF0WzJdKQoJYXRbMl09Y291bnQ7Cglmb3IoaT0zO2k8PXNxcnQobik7aT1pKzIpCgl7CgkJY291bnQ9MDsKCQl3aGlsZShuJWk9PTApCgkJewoJCQljb3VudCsrOwoJCQluPW4vaTsKCQl9CgkJaWYoY291bnQ+YXRbaV0pCgkJYXRbaV09Y291bnQ7Cgl9CglpZihuPjIpCgl7CgkJaWYoYXRbbl09PTApCgkJYXRbbl09MTsKCX0KfQppbnQgbWFpbigpCnsKCWxsIHQsbixpLGssY291bnQ7CglsbCBhclsxMDAwMDVdOwoJc2NhbmYoIiVsbGQiLCZ0KTsKCXdoaWxlKHQtLSkKCXsKCQlmb3IoaT0wO2k8MTAwMDAwNTtpKyspCgkJYXRbaV09MDsKCQljb3VudD0wOwoJCXNjYW5mKCIlbGxkIiwmbik7CgkJZm9yKGk9MDtpPG47aSsrKQoJCXNjYW5mKCIlbGxkIiwmYXJbaV0pOwoJCWZvcihpPTA7aTxuO2krKykKCQlwcmltZShhcltpXSk7CgkJZm9yKGk9MDtpPD0xMDAwMDA1O2krKykKCQljb3VudD1jb3VudCthdFtpXTsKCSAgICBwcmludGYoIiVsbGRcbiIsY291bnQpOwoJfQoJcmV0dXJuIDA7CgkKfQ==