#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;
}
I2luY2x1ZGU8c3RkaW8uaD4KI2luY2x1ZGU8bWF0aC5oPgojaW5jbHVkZTxzdHJpbmcuaD4KdHlwZWRlZiBsb25nIGxvbmcgbGw7CmxsIGF0WzEwMDAwMDVdPXswfTsKbGwgcHJpbWUobGwgbikKewoJbGwgaSxjb3VudD0wOwoJd2hpbGUobiUyPT0wKQoJewoJCWNvdW50Kys7CgkJbj1uLzI7Cgl9CglhdFsyXT1jb3VudDsKCWNvdW50PTA7Cglmb3IoaT0zO2k8PXNxcnQobik7aT1pKzIpCgl7CgkJd2hpbGUobiVpPT0wKQoJCXsKCQkJY291bnQrKzsKCQkJbj1uL2k7CgkJfQoJCWF0W2ldPWNvdW50OwoJCWNvdW50PTA7Cgl9CglpZihuPjIpCgl7CgkJY291bnQrKzsKCQlhdFtuXT1jb3VudDsKCX0KfQppbnQgbWFpbigpCnsKCWxsIHQsbixpLGssY291bnQ7CglsbCBhclsxMDAwMDVdOwoJc2NhbmYoIiVsbGQiLCZ0KTsKCXdoaWxlKHQtLSkKCXsKCQltZW1zZXQoYXQsMCxzaXplb2YoYXQpKTsKCQljb3VudD0wOwoJCXNjYW5mKCIlbGxkIiwmbik7CgkJZm9yKGk9MDtpPG47aSsrKQoJCXNjYW5mKCIlbGxkIiwmYXJbaV0pOwoJCWZvcihpPTA7aTxuO2krKykKCQlwcmltZShhcltpXSk7CgkJZm9yKGk9MDtpPD0xMDAwMDA1O2krKykKCQlpZihhdFtpXSE9MCkKCQljb3VudD1jb3VudCthdFtpXTsKCQkJCXByaW50ZigiJWxsZFxuIixjb3VudCk7Cgl9CglyZXR1cm4gMDsKCQp9