#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;
using i128 = __int128_t;

const int N = 3e5 + 10;

int n;
i128 a[N];

i128 read() {
	i128 x = 0; int ch = getchar();
	while (!isdigit(ch)) ch = getchar();
	while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
	return x;
}

mt19937 Rnd(time(0));
int Rand(int l, int r) { return Rnd() % (r - l + 1) + l;} 
bool isPrime(int n) { for (int i = 2; i * i <= n; ++i) if (n % i == 0) return 0; return 1;}
int Pow(int x, int y, int p) {
	int r = 1;
	for (; y; y >>= 1, x = 1ll * x * x % p) if (y & 1) r = 1ll * r * x % p;
	return r;
}

ull v[N];
vector<ull> val;
vector<int> vec[N];

bool np[N];
int tot = 0, prm[N];
int f[N];

int main() {
	n = read();
	for (int i = 1; i <= n; ++i) a[i] = read();
	
	for (int t = 0; t < 64; ++t) {
		int p = Rand(1e5, 3e5);
		while (!isPrime(p)) p = Rand(1e5, 3e5);
		f[0] = f[1] = 1, tot = 0;
		for (int i = 2; i < p; ++i) {
			if (!np[i]) { prm[++tot] = i, f[i] = Pow(i, (p - 1) / 2, p);}
			for (int j = 1, t; (t = i * prm[j]) < p; ++j) {
				np[t] = 1, f[t] = 1ll * f[i] * f[prm[j]] % p;
				if (i % prm[j] == 0) break;
			}
		}
		for (int i = 1; i <= n; ++i) {
			v[i] ^= (f[a[i] % p] == 1 ? 0 : (i128)1) << t;
		}
	}
	for (int i = n; i >= 1; --i) v[i] ^= v[i + 1];
	
	for (int i = 1; i <= n + 1; ++i) val.push_back(v[i]);
	sort(val.begin(), val.end());
	for (int i = 1; i <= n + 1; ++i) v[i] = lower_bound(val.begin(), val.end(), v[i]) - val.begin();

	long long ans = 0;
	vec[0].push_back(n + 1);
	for (int i = n; i >= 1; --i) {
		ans += vec[v[i]].size();
		vec[v[i]].push_back(i);
	}
	
	cout << ans << endl;
	int cnt = 1e5;
	for (int i = 1; i <= n; ++i) {
		vec[v[i]].pop_back();
		for (int j = (int)vec[v[i]].size() - 1; j >= 0; --j) {
			if (cnt == 0) { return 0;}
			cout << i << ' ' << vec[v[i]][j] - 1 << endl;
			--cnt;
		}
	}
	
	return 0;
}