#include <cmath>
#include <iostream>
#include <limits>
#include <unordered_set>
#include <vector>

struct candidate {
	long long value = std::numeric_limits<long long>::max();
	bool has = false;

	void consider(long long v) {
		if (!has) {
			value = v;
			has = true;
		} else {
			if (abs(value) > abs(v)) {
				value = v;
			} else if (v > 0 && value==-v) {
				value = v;
			}
		}
	}
};

std::vector<bool> positive_seen(1);
std::vector<bool> negative_seen(1);

long long max_value = 0;
long long min_value = 0;

long long pos_unseen = 1;
long long neg_unseen = -1;

bool seen(long long v) {
	if (v >= 0) {
		if (positive_seen.size() <= v) {
			return false;
		} else {
			return positive_seen[v];
		}
	} else {
		if (negative_seen.size() <= -v) {
			return false;
		} else {
			return negative_seen[-v];
		}
	}
}

void see(long long v) {
	if (v >= 0) {
		while (positive_seen.size() <= v) {
			positive_seen.resize(2 * positive_seen.size());
		}
		positive_seen[v] = true;

		if (max_value < v) {
			max_value = v;
		}

		while (seen(pos_unseen)) {
			pos_unseen++;
		}
	} else {
		while (negative_seen.size() <= -v) {
			negative_seen.resize(2 * negative_seen.size());
		}
		negative_seen[-v] = true;

		if (min_value > v) {
			min_value = v;
		}

		while (seen(neg_unseen)) {
			neg_unseen--;
		}
	}
}

long long up_jump = 1;
long long down_jump = -1;

long long other(long long p) {
	see(p);
	if (p==0) {
		return 1;
	} else {
		candidate c;
		long long v;

		if (p > 0) {
			for (long long r = 1;; r++) {
				v = p + r*r;
				if (!seen(v)) {
					c.consider(v);
				}
				if (v > max_value) {
					break;
				}
			}
			for (long long r = 1;; r++) {
				v = p - r*r;
				if (!seen(v)) {
					c.consider(v);
				}
				if (v < pos_unseen) {
					break;
				}
			}
			for (;;) {
				v = p + down_jump*abs(down_jump);
				if (neg_unseen < v) {
					down_jump--;
				} else {
					break;
				}
			}
			long long r = down_jump;
			while (p + r*abs(r) < neg_unseen) {
				r++;
			}
			for (;;) {
				v = p + r*abs(r);
				if (!seen(v)) {
					c.consider(v);
				}
				if (v < min_value) {
					break;
				}
				r--;
			}
		} else {
			for (long long r = 1;; r++) {
				v = p + r*r;
				if (!seen(v)) {
					c.consider(v);
				}
				if (v > neg_unseen) {
					break;
				}
			}
			for (long long r = 1;; r++) {
				v = p - r*r;
				if (!seen(v)) {
					c.consider(v);
				}
				if (v < min_value) {
					break;
				}
			}
			for (;;) {
				v = p + up_jump*abs(up_jump);
				if (v < pos_unseen) {
					up_jump++;
				} else {
					break;
				}
			}
			long long r = up_jump;
			while (p + r*abs(r) > pos_unseen) {
				r--;
			}
			for (;;) {
				v = p + r*abs(r);
				if (!seen(v)) {
					c.consider(v);
				}
				if (v > max_value) {
					break;
				}
				r++;
			}
		}

		return c.value;
	}
}

int main() {
	long long m = 0;
	long long v = 0;

	for (long long n = 0; m < 10'000; n++) {
		v = other(v);

		long long mi = std::max(-neg_unseen, pos_unseen);
		long long mx = std::min(-min_value, max_value);

		long long nb = 0;
		for (long long v = mi; v <= mx; v++) {
			if (!seen(v) && !seen(-v)) {
				nb++;
			}
		}

		if (nb) {
			std::cout << ++m << ' ' <<  nb << std::endl;
		}
	}

	return 0;
}