#include <iostream>
#include<vector>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
vector<int>arr(n+1);
arr[0]=0;
for(int i=1;i<=n;i++)
cin>>arr[i];
vector<int>startindex(n+1,0);
vector<int>primearr(1001,0);
for(int i=1;i<=n;i++)
{
int seen=0;
int pr=arr[i];
vector<int>primes;
if(pr%2==0)
{
while(pr%2==0)
{
primes.push_back(2);
pr=pr/2;
}
}
for(int j=3;j*j<=pr;j+=2)
{
while(pr%j==0)
{
primes.push_back(j);
pr=pr/j;
}
}
if(pr>1)
primes.push_back(pr);
for(int j=0;j<primes.size();j++)
{
int pr1=primes[j];
if(primearr[pr1]>seen)
seen=primearr[pr1];
primearr[pr1]=i;
}
startindex[i]=(seen>startindex[i-1]?seen:startindex[i-1]);
primes.clear();
}
long long count=0;
for(int i=1;i<=n;i++)
{
count=count+(i-startindex[i]);
}
cout<<count<<endl;
}
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZTx2ZWN0b3I+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKCgppbnQgbWFpbigpCnsKICAgIGludCB0OwogICAgY2luPj50OwogICAgd2hpbGUodC0tKQogICAgewogICAgICAgIGludCBuOwogICAgICAgIGNpbj4+bjsKICAgICAgICB2ZWN0b3I8aW50PmFycihuKzEpOwogICAgICAgIGFyclswXT0wOwogICAgICAgIGZvcihpbnQgaT0xO2k8PW47aSsrKQogICAgICAgIGNpbj4+YXJyW2ldOwogICAgICAgIHZlY3RvcjxpbnQ+c3RhcnRpbmRleChuKzEsMCk7CiAgICAgICAgdmVjdG9yPGludD5wcmltZWFycigxMDAxLDApOwoKICAgICAgICBmb3IoaW50IGk9MTtpPD1uO2krKykKICAgICAgICB7CiAgICAgICAgICAgIGludCBzZWVuPTA7CiAgICAgICAgICAgIGludCBwcj1hcnJbaV07CiAgICAgICAgICAgIHZlY3RvcjxpbnQ+cHJpbWVzOwogICAgICAgICAgICBpZihwciUyPT0wKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICB3aGlsZShwciUyPT0wKQogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgIHByaW1lcy5wdXNoX2JhY2soMik7CiAgICAgICAgICAgICAgICAgICAgcHI9cHIvMjsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQogICAgICAgICAgICBmb3IoaW50IGo9MztqKmo8PXByO2orPTIpCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIHdoaWxlKHByJWo9PTApCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgcHJpbWVzLnB1c2hfYmFjayhqKTsKICAgICAgICAgICAgICAgICAgICBwcj1wci9qOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CiAgICAgICAgICAgIGlmKHByPjEpCiAgICAgICAgICAgIHByaW1lcy5wdXNoX2JhY2socHIpOwogICAgICAgICAgICBmb3IoaW50IGo9MDtqPHByaW1lcy5zaXplKCk7aisrKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBpbnQgcHIxPXByaW1lc1tqXTsKICAgICAgICAgICAgICAgIGlmKHByaW1lYXJyW3ByMV0+c2VlbikKICAgICAgICAgICAgICAgIHNlZW49cHJpbWVhcnJbcHIxXTsKICAgICAgICAgICAgICAgIHByaW1lYXJyW3ByMV09aTsKICAgICAgICAgICAgfQogICAgICAgICAgICBzdGFydGluZGV4W2ldPShzZWVuPnN0YXJ0aW5kZXhbaS0xXT9zZWVuOnN0YXJ0aW5kZXhbaS0xXSk7CiAgICAgICAgICAgIHByaW1lcy5jbGVhcigpOwogICAgICAgIH0KICAgICAgICBsb25nIGxvbmcgY291bnQ9MDsKICAgICAgICBmb3IoaW50IGk9MTtpPD1uO2krKykKICAgICAgICB7CiAgICAgICAgICAgIGNvdW50PWNvdW50KyhpLXN0YXJ0aW5kZXhbaV0pOwogICAgICAgIH0KICAgICAgICBjb3V0PDxjb3VudDw8ZW5kbDsKICAgIH0KICAgIHJldHVybiAwOwp9Cg==