#include <cctype>
#include <cstdio>
#include <cstring>
#include <random>
#include <unordered_map>
using namespace std;

int main() {
    typedef unsigned long long ull;
    static const int maxn = 300010, L = 10000, R = 100000;
    int n;
    scanf("%d", &n);
    static __int128 a[maxn];
    for (int i = 1; i <= n; i++) {
        char ch = getchar();
        while (!isdigit(ch)) ch = getchar();
        while (isdigit(ch)) a[i] = a[i] * 10 + ch - '0', ch = getchar();
    }
    static bool vis[R];
    static ull msk[maxn];
    for (int t = 0; t < 64; t++) {
        int p;
        static random_device rd;
        static mt19937 rng(rd());
        while (true) {
            bool flag = !vis[p = rng() % (R - L) + L];
            for (int i = 2; i * i <= p && flag; i++)
                if (!(p % i))
                    flag = false;
            if (flag)
                break;
        }
        static bool flag[R];
        memset(flag, 0, sizeof(flag));
        for (int i = 1; i < p; i++) flag[(long long)i * i % p] = true;
        bool cur = false;
        for (int i = 1; i <= n; i++) {
            auto x = a[i];
            while (!(x % p)) x /= p;
            msk[i] ^= (ull)(cur ^= !flag[x % p]) << t;
        }
    }
    long long ans = 0;
    static unordered_map<ull, vector<int>> cnt;
    for (int i = 0; i <= n; i++) cnt[msk[i]].push_back(i);
    for (auto& p : cnt) ans += p.second.size() * (p.second.size() - 1ll) >> 1;
    printf("%lld\n", ans);
    for (int l = 1, c = 0; l <= n && c < 100000; l++)
        for (int r : cnt[msk[l - 1]])
            if (l <= r) {
                printf("%d %d\n", l, r);
                if (++c == 100000)
                    break;
            }
    return 0;
}