#include <iostream>
#include <fstream>
using namespace std;

ifstream fin("pairs.in");
ofstream fout("pairs.out");

const int MAX_N = 100100;
const int MAX_V = 1000100;

int n, value, soln, nr;

int a[MAX_N];
int dv[MAX_N];
int card[MAX_V];


void read() {
	fin >> n;
	for (int i = 1; i <= n; ++i) {
		fin >> a[i];
	}
	fin.close();
}


inline void check() {
	if (nr) {
		soln = soln + card[value] * (nr % 2 == 1 ? -1 : 1);
		++card[value];
	}
}

void gen(const int &k) {
	if (k > dv[0])
		check();
	else
		for (int i = 0; i <= 1; ++i) {
			if (i)
				value = value * dv[k], ++nr;
			gen(k + 1);
			if (i)
				value = value / dv[k], --nr;
		}
}

void solve() {
	for (int i = 1; i <= n; ++i) {
		int d = a[i];
		dv[0] = 0;
		
		for (int j = 2; j * j <= a[i] && d > 1; ++j) {
			while (d % j == 0) {
				dv[++dv[0]] = j;
				d /= j;
			}
		}
		if (d > 1)
			dv[++dv[0]] = d;
		
		if (a[i] > 1) {
			soln += i - 1;
			value = 1; nr = 0;
			gen(1);
		} else {
			++card[1];
		}
	}
}


void write() {
	fout << soln << '\n';
	fout.close();
}


int main() {
	read();
	solve();
	write();
}