//洛谷 P10063
//https://www.luogu.com.cn/problem/P10063
#include<bits/stdc++.h>
#include<bits/extc++.h>
#define LL long long
#define ull unsigned long long
#define bll __int128
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
using namespace __gnu_pbds;
mt19937 rnd(time(0));
const int N=3e5+5,B=50;
inline bll rd()
{
	bll x=0;char ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return x;
}
int n,b[N],pr[N],tot,e[N];ull d[N],ans;bool v[N*4];bll a[N];
gp_hash_table<ull,vector<int>>mp;
inline void init(int M=1e6)
{
	for(int i=2;i<=M;i++)
	{
		if(!v[i]) pr[++pr[0]]=i;
		for(int j=1;j<=pr[0]&&i*pr[j]<=M;j++)
		{
			v[i*pr[j]]=1;
			if(i%pr[j]==0) break;
		}
	}int cnt=0;
	for(int i=1;i<=pr[0];i++) if(5e5<=pr[i]&&pr[i]<=1e6) b[++cnt]=pr[i];
	shuffle(b+1,b+1+cnt,rnd);
}
inline void get(int t)
{
	const unsigned mod=b[t];fill(v+0,v+1+mod,1);
	for(int i=0;i<mod;i++) v[1ll*i*i%mod]=0;
	for(int i=1;i<=n;i++)
	{
		bll x=a[i];while(x%mod==0) x/=mod;
		if(v[x%mod]) d[i]|=(1ll<<t);
	}
}
int main()
{
	init();scanf("%d",&n);for(int i=1;i<=n;i++) a[i]=rd();
	for(int i=1;i<=B;i++) get(i);
	for(int i=1;i<=n;i++) d[i]^=d[i-1];
	for(int i=0;i<=n;i++) mp[d[i]].push_back(i),e[i]=mp[d[i]].size();
	for(int i=0;i<n;i++) ans+=mp[d[i]].size()-e[i];printf("%llu\n",ans);
	for(int i=0;i<n;i++)
	{
		vector<int>g=mp[d[i]];
		for(int j=e[i];j<g.size();j++){printf("%d %d\n",i+1,g[j]);if(++tot==1e5) return 0;}
	}
	return 0;
}