#include <iostream>

// largest integer with binary expansion of the form (01)*.
long long get_mask() {
	long long m = 0;
	for (long long b = 1; b; b <<= 2) {
		m |= b;
	}
	return m;
}

long long mask = get_mask();

bool is(long long n) {
	long long x = n & mask;
	return x==0 || x==n;
}

long long a(long long n) {
	for (long long k = 1;; k++) {
		if (is(k*n)) {
			return k;
		}
	}
}

int main() {
	for (long long n = 0; n <= 10'000; n++) {
		std::cout << n << ' ' << a(n) << std::endl;
	}

	return 0;
}