#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

#include <cstdio>

struct istream {
    static const size_t SIZE = 1<<18;
    char buf[SIZE], *cur, *end;

    istream() {
        cur = end = buf;
    }

    char get() {
        if (cur == end) {
            end = buf + fread(buf, 1, SIZE, stdin);
            if (end == cur) return EOF;
        }
        return *(cur++);
    }

    template<typename T>
    istream& operator>>(T& x) {
        x = 0;
        char c;
        do c = get(); while (c < 48 || c > 57);
        do {x = (x << 3) + (x << 1) + (c ^ 48); c = get();} while (c > 47 && c < 58);
        return *this;
    }
} cin;

using std::cout;

using i32 = int;
using i64 = long long;

static i32 gcd(i32 a, i32 b) {
    while (b) {
        a = a % b;
        std::swap(a, b);
    }
    return a;
}

#define V 2000001
#define N 2000001

std::vector<i32> ans[V];

i32 f[N], t[N];

void solve(const i32& tim) {
    i32 n;
    i64 res = 0;
    cin >> n;
    for (i32 i = 1; i <= n; ++ i) {
        i32 x;
        cin >> x;
        if (t[x] != tim) t[x] = tim, f[x] = 0;
        else res += f[x];
        for (const auto& v : ans[x]) {
            // cout<< v << ' ';
            if (t[v] != tim) t[v] = tim, f[v] = 0;
            ++f[v];
        }
        // cout<< '\n';
    }
    cout << res << '\n';
}

int main() {
    std::ios::sync_with_stdio(false);
    cout.tie(nullptr);

    for (i32 i = 2; i <= 1000000; ++ i) {
        ans[i].emplace_back(i ^ 1);
        for (i32 j = 2, lim = sqrt(i); j <= lim; ++ j) {
            if (i % j == 0) {
                if ((i ^ j) < V && gcd(i ^ j, i) == j) ans[i ^ j].emplace_back(i);
                if (i / j != j && (i ^ (i/j)) < V && gcd(i ^ (i/j), i) == (i/j)) 
                    ans[i ^ (i/j)].emplace_back(i); 
            }
        }
    }

    // for (i32 i = 1; i <= 10; ++ i) {
    //     for (const auto& x : ans[i]) cout << x << ' ';
    //     cout << '\n';
    // }

    // i32 t;
    // cin >> t;
    // while (t--) solve(t);

    return 0;
}