//洛谷 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;
}