文件目录

// 完全平方数 异或运算，为0
// 分解质因数，偶数个质数互相抵消
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, a[100050];
int s[100050];   // 异或前缀区间
map<int, int> m; // 统计相同剩余奇数质数部分
int ans = 0;
int fj(int k)
{
    int prime = 0; // 统计质数组成部分，每个二进制位代表一个质数
    int p[] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
    for (int i = 1; i < 11 && p[i] <= k; i++)
    {
        while (k % p[i] == 0)
        {
            prime ^= (1 << i);
            k /= p[i];
        }
    }
    return prime;
}
signed main()
{
    scanf("%d", &n);
    m[0] = 1;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", a + i);
        s[i] = s[i - 1] ^ fj(a[i]); // 分解质因数 a[i]，剩余质数与前缀异或
        //cout << s[i] << " ";
        ans += m[s[i]];
        m[s[i]]++;
    }
    cout << ans;
    return 0;
}