SQUARE(DHBB)

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
//New start, best wishes
const int N = 5e6;
int n, a[N+1], c[N+1], d[N+1];
bool b[N+1];
using namespace std;
vector<int> prime;
void sieve()
{
    fill (b + 1, b + n + 1, true);
    fill (a + 1, a + n + 1, 1);
    fill(d +1, d + n + 1, 0);
    iota(c + 1, c + n + 1, 1);
    for (int i = 2; i <= n; ++ i)
    {
        if (b[i])
        {
            for (int j = i; j <= n; j += i)
            {
                b[j] = false;
                int cnt = 0;
                while (c[j] % i == 0)
                {
                    c[j] /= i;
                    ++cnt;
                }
                cnt = cnt % 2;
                if (cnt == 1)
                {
                    a[j] *= i;
                }
            }
        }
    }
}
void read()
{
    cin >> n;
    sieve();
}
void solve()
{
    a[1] = 1;
    long long ans = 0;
    for (int i = 1; i <= n; ++ i)
    {
        ans += (long long)d[a[i]] * (d[a[i]] - 1)/2;
        ++d[a[i]];
    }
    cout << ans;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //freopen("SQUARE.INP", "r", stdin);
    //freopen("SQUARE.OUT", "w", stdout);
    read();
    solve();
}