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
#include <bits/stdc++.h>
using namespace std;

#define FOR(i, l, r) for(int i = (l); i <= (r); ++i)
#define REP(i, n) FOR(i, 0, (n) - 1)
#define ssize(x) int(x.size())
#ifdef DEBUG
auto &operator << (auto &o, pair<auto, auto> p) {
	return o << "(" << p.first << ", " << p.second << ")";
}
auto operator << (auto &o, auto x) -> decltype(x.end(), o) {
	o << "{"; int i = 0;
	for (auto e : x) o << ","+!i++ << e;
	return o << "}";
}
#define debug(X...) cerr << "["#X"]: ", [](auto ...$) {((cerr << $ << "; "), ...) << endl;}(X)
#else
#define debug(...) {}
#endif

long long sq(int a) {
	return 1LL * a * a;
}

bool is_square(int n) {
	int s = sqrt(n);
	return (s * s == n);
}

vector<int> sieve;

void calc_sieve(int n) {
	sieve = vector<int>(n + 1);
	for (int i = 2; i * i <= n; ++i) {
		if (sieve[i] == 0)
			for (int j = i * i; j <= n; j += i)
				if (sieve[j] == 0) sieve[j] = i;
	}
}

vector<pair<int, int>> get_factors(int n) {
	vector<pair<int, int>> factors;
	auto add_factor = [&](int p) {
		if (!factors.empty() and factors.back().first == p)
			factors.back().second++;
		else 
			factors.emplace_back(p, 1);
	};

	while (sieve[n] != 0) {
		int p = sieve[n];
		add_factor(p);
		n /= p;
	}
	add_factor(n);

	return factors;
}

int jacobi(int n) {
	vector<pair<int, int>> factors = get_factors(n);

	int r = 4;
	for (auto [p, e] : factors) {
		if (p % 4 == 1)
			r *= (e + 1);
		else if (p % 4 == 3 and e % 2 != 0)
			return 0;
	}

	if (is_square(n)) r -= 4;

	if (n % 2 == 0 and is_square(n / 2))
		r += 4;

	return r / 8;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int n; cin >> n;
	calc_sieve(n * n + 5);
	debug(sieve);

	int answer = 0;
	FOR (t, 1, n) {
		int k = t * t;
		FOR (h, 1, n) {
			int l = k - h * h;
			if (l <= 0) break;

			int j = jacobi(l);
			debug(l, j);
			answer += j;
		}
	}

	cout << answer << '\n';
}