C++ :

#include <bits/stdc++.h>
using namespace std;

int n, a[100005], b[35], prexor;
long long ans, cnt[1 << 10];
vector <int> prime = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};

void read(int &a, int ch = 0) {
	while (!isdigit(ch = getchar()));
	for (a = 0; isdigit(ch); ch = getchar()) a = (a << 3) + (a << 1) + (ch ^ 48);
}
void prework() {
	// 预处理数组 b
	for (int i = 1; i <= 30; i++) {
		int j = i;
		for (int k = 0; k < 10; k++) {
			while (j % prime[k] == 0) {
				b[i] ^= 1 << k;
				j /= prime[k];
			}
		}
	}
}
int main() {
	prework();
	read(n);
	cnt[0] = 1;
	for (int i = 1; i <= n; i++) {
		read(a[i]);
		prexor ^= b[a[i]];
		ans += cnt[prexor]++;
	}
	cout << ans;
	return 0;
}