1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define ALL(x) begin(x), end(x)
#define SZ(x) (int)(x).size()
#define st first
#define nd second
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;

#ifdef LOCAL
#define DTP(x, y)                                    \
    auto operator<<(auto &o, auto a)->decltype(y, o) \
    {                                                \
        o << "(";                                    \
        x;                                           \
        return o << ")";                             \
    }
DTP(o << a.first << ", " << a.second, a.second);
DTP(for (auto i : a) o << i << ", ", ALL(a));
void dump(auto... x) { ((cerr << x << ", "), ...) << '\n'; }
#define debug(x...) cerr << setw(4) << __LINE__ << ":[" #x "]: ", dump(x)
#else
#define debug(...) 42
#endif

void solve()
{
    int n;
    cin >> n;
    vi U(n * n + 1, 0);
    for (int i = 1; i < SZ(U); i++)
    {
        int cnt = 0, t = i;
        while (!(t & 1))
        {
            t /= 2;
            cnt++;
        }
        U[i] = cnt & 1;
    }
    // debug(V);
    // debug(U);
    vi S(n * n + 1, 0);
    for (int i = 1; i < SZ(S); i++)
    {
        // debug(S);
        int why = sqrt(i);
        if (why * why == i || (why + 1) * (why + 1) == i || (why - 1) * (why - 1) == i)
            S[i]--;
        for (int j = 1; j * i < SZ(S); j++)
        {
            if ((i & 3) == 1)
                S[i * j]++;
            else if ((i & 3) == 3)
                S[i * j]--;
        }
    }
    for (int i = 1; i < SZ(S); i++)
        S[i] = (S[i] + U[i]) / 2;
    // debug(S);
    vl ANS(n + 1, 0);
    for (int i = 1; i <= n; i++)
    {
        if (!(i & 1))
        {
            ANS[i] = ANS[i / 2];
            continue;
        }
        for (int j = 1; j < i; j++)
        {
            int val = i * i - j * j;
            // if (V[val])
            {
                // debug(i, j, val);
                ANS[i] += S[val];
            }
        }
    }
    // for (auto &a : ANS)
    //     cout << ',' << a;
    // cout << endl;
    // debug(ANS);
    ll ans = 0;
    for (auto &a : ANS)
        ans += a;
    cout << ans << endl;
}

main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    int Z = 1;
    // cin >> Z;
    while (Z--)
        solve();
}