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
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

//#pragma GCC optimize("O0")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native")
#pragma GCC optimize("unroll-loops")

using namespace std;
//using namespace __gnu_pbds;

#define pb push_back
#define F first
#define S second
#define ll long long
#define ld double long
#define ull unsigned long long
//#define endl '\n'


const ll N = 5e4 + 36;
const ll M = 2e3 + 36;
const ll INF = 1e9 + 7;
const ll MOD = 1e9 + 7;
const ll MOD1 = 888888901;
const ll MOD2 = 999988901;
const ll X[8] = {1, -1, 2, 2, -2, -2, 1, -1};
const ll Y[8] = {2, 2, 1, -1, 1, -1, -2, -2};
const ld PI = 3.14159265358979323846;
const ld EPS = 1e-10;

//tree < pair < string, int >, null_type, less < pair < string, int > >, rb_tree_tag, tree_order_statistics_node_update > a;

//mt19937 gen(chrono::system_clock::now().time_since_epoch().count());
mt19937 gen(19937);

signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
#endif // LOCAL
    int n = 5000;
    cin >> n;
    int ss = sqrt((n * n) * 3);

    vector<int> mp(50000001, 0);
    vector<pair<int, int>> lol;
    for (int i(1); i <= n; ++i) {
        for (int j(1); j <= n; ++j) {
            mp[i * i + j * j]++;
            lol.pb({i, i * i + j * j});
        }
    }
    reverse(lol.begin(), lol.end());
    int k = 0;

    /*for (int i(1); i <= n; ++i){
        for (int j(i); j <= n; ++j) {
            for (int l(1); l <= n; ++l) {
                ll x = i * i + j * j + l * l;
                //if (sqr.find(x) != sqr.end()) {
                int y = sqrt(x);
                if (y <= n && y * y == x) {
                    ++k;
                    cout << i << ' ' << j << ' ' << l << endl;
                }
                //}
            }
        }
    }
    cout << k << endl;*/

    int ans = 0;
    for (int i(1); i <= n; ++i) {
        for (int j(i); j <= n; ++j) {
            if (50000000 >= j * j - i * i)
            ans += mp[j * j - i * i];
        }
        while (lol.size() && lol.back().F == i) {
            --mp[lol.back().S];
            lol.pop_back();
        }
    }

    cout << ans << endl;


    return 0;
}