#include <bits/stdc++.h>
using namespace std;
int prime[100001] = {0};
int k[100001] = {0};
void Sieve() {
    for (int i = 1; i < 100001; i++)
        k[i] = i;

    for (int i = 2; i < 100001; i++) {
    if (prime[i] == 0) {
    for (int j = i; j < 100001; j += i) {
    prime[j] = 1;
    while (k[j] % (i * i) == 0)
    k[j] /= (i * i);
            }
        }
    }
}

int countPairs(int arr[], int n) {
    unordered_map<int, int> freq;
    for (int i = 0; i < n; i++) {
        freq[k[arr[i]]]++;
    }

    int sum = 0;
    for (auto i : freq) {
        sum += ((i.second - 1) * i.second) / 2;
    }

    return sum;
}

int main() {
    int n;
    cin >> n;
    int arr[n];
    for (int i = 0; i < n; i++) {
        arr[i] = i + 1;
    }

    Sieve();
    cout << n + 2 * countPairs(arr, n) << endl;

    return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll maxPyramidHeight(ll N, vector<ll>& arr) {
    sort(arr.begin(), arr.end());
    ll height = 0;
    ll blocks_used = 0;
    ll current_level_blocks = 1;
        while (blocks_used + current_level_blocks <= N) {
        blocks_used += current_level_blocks;
        height++;
        current_level_blocks++;
    }
    return height;
}

def bitByBit(input1, input2):
    n, a = input1, input2
    o = set()
    for i in range(n):
        c = 0
        for j in range(i, n):
            c |= a[j]
            o.add(c)
    m = float('inf')
    l = list(o)
    k = len(l)
    for i in range(k):
        for j in range(i + 1, k):
            m = min(m, l[i] ^ l[j])
    return m if m != float('inf') else 0

#include <bits/stdc++.h>
using namespace std;
int solve(int n) {
    if (n <= 0) return 1;  
    return (1 << (int)(log2(n - 1) + 1));
}
int main() {
    int N;
    cin >> N; 
    vector<int> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i]; 
    }
    vector<int> squaredA(N);
    for (int i = 0; i < N; i++) {
        squaredA[i] = A[i] * A[i]; 
    }
    vector<int> setBits(N);
    int minSetBits = INT_MAX;
    int maxSetBits = INT_MIN;
    int X, Y;
    for (int i = 0; i < N; i++) {
    setBits[i] = __builtin_popcount(squaredA[i]);  
    if (setBits[i] < minSetBits) {
    minSetBits = setBits[i];
    Y = squaredA[i];  
    }
    if (setBits[i] > maxSetBits) 
    {
    maxSetBits = setBits[i];
    X = squaredA[i]; 
    }
    }
    int product = X * Y;
    int result = solve(product);
    cout << result << endl;
    return 0;
}