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

int main(){
    int n ; cin >> n;

    vector<int> nums(n);
    for(int &num : nums) cin >> num;

    int maxE = *max_element(nums.begin() , nums.end());
    
    // build SPF array
    vector<int> SPF(maxE + 1);
    iota(SPF.begin() , SPF.end() , 0);

    for(int num = 2 ; num * num <= maxE ; num++){
    	if(SPF[num] == num){
    		for(int F = num * num ; F <= maxE ; F += num) if(SPF[F] == F) SPF[F] = num;
    	}
    }
	
    // map every prime number to its positon/index
    int primeId = 0;
    vector<int> primeIndex(maxE + 1);
    for(int num = 2 ; num <= maxE ; num++){
    	if(SPF[num] == num) primeIndex[num] = primeId++;
    }

    long long subarrays = 0;

    bitset<9600> prod = 0;
    unordered_map<bitset<9600> , int> prefixCnt = { {prod , 1} };

    for(int num : nums){
    	int curr = num;
        while(curr != 1){
            int prime = SPF[curr];
            int expo = 0;
            while(curr % prime == 0){
                curr /= prime;
                expo += 1;
            }
            if(expo & 1) prod.flip(primeIndex[prime]);
        }
        subarrays += prefixCnt[prod]++;
    }

    cout << subarrays;

    return 0;
}