#include<bits/stdc++.h>
#define LL __int128
using namespace std;
const int N=300000,M=5000000;
int n,ct=0,pt,pr[M+5];
bool z[M+5],ys[M+5];
LL a[N+5];
long long ans=0,v[N+5];
vector<int>g[N+5];
map<long long,int>mp;
void rd(LL &t){
	char ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9'){
		t=t*10+ch-'0';
		ch=getchar();
	}
}
void init(){
	for(int i=2;i<=M;i++){
		if(i>1e5&&!pt) pt=pr[0];
		if(!z[i]) pr[++pr[0]]=i;
		for(int j=1;j<=pr[0]&&i*pr[j]<=M;j++){
			z[i*pr[j]]=1;
			if(i%pr[j]==0) break;
		}
	}
}
int main()
{
	srand(time(NULL));
	scanf("%d",&n);
	for(int i=1;i<=n;i++) rd(a[i]);
	init();
	for(int o=0,p;o<40;o++){
		if(o<=30) p=pr[rand()%pt+1];
		else p=pr[rand()%(pr[0]-pt)+pt+1];
//		cout << p << ">>\n"; 
		memset(ys,0,sizeof(ys));
		for(int i=1;i<=(p+1)/2;i++) ys[1ll*i*i%p]=1;
		for(int i=1;i<=n;i++){
			LL x=a[i];
			while(x%p==0) x/=p;
			v[i]^=(ys[x%p]^1)*(1ll<<o);
		}
	}
	for(int i=1;i<=n;i++) v[i]^=v[i-1];
	for(int i=0;i<=n;i++){
		if(!mp[v[i]]) mp[v[i]]=++ct;
		g[mp[v[i]]].emplace_back(i);
	}
	for(int i=1;i<=ct;i++){
		ans+=1ll*g[i].size()*(g[i].size()-1)/2;
	}
	printf("%lld\n",ans);
	int tmp=0;
	for(int i=1;i<=n;i++){
		int tw=mp[v[i-1]];
		for(int j:g[tw]){
			if(i<=j){
				printf("%d %d\n",i,j);
				++tmp;
				if(tmp==100000) break;
			}
		}
		if(tmp==100000) break;
	}
	return 0;
}