#include <algorithm>
#include <cmath>
#include <iostream>
#include <stdlib.h>
#include <string.h>
using namespace std;

void move(long long &x, long long &y) {
	long long w = max(abs(x), abs(y));

	if (y==-w) {
		x++;
	} else if (x==-w) {
		y--;
	} else if (y==w) {
		x--;
	} else {
		y++;
	}
}

inline long long square(long long v) {
	return v*v;
}

long long index(long long x, long long y) {
	if (x>abs(y)) {
		return 1 + square(2*x-1) + (x+y-1);
	} else if (x>y) {
		return 1 + 2*-y*(1-2*y) + (x-y);
	} else if (y>=abs(x)) {
		return 1 + 2*y*(2*y-1) + (y-x);
	} else {
		return 1 + 4*square(x) + (-y-x);
	}
}

#define MAX (1LL<<33)
bool *sieve = 0;

bool is(long long x, long long y, long long w2) {
	long long dx = 0;
	long long dy = 0;

	for (long long s=w2; s>0; s--) {
		long long k = index(x+dx, y+dy);

		if (k>=MAX) {
			exit(0);
		} else if (!sieve[k]) {
			return false;
		}

		move(dx, dy);
	}

	return true;
}

int main() {
	sieve = new bool[MAX];
	memset(sieve, 0, MAX*sizeof(*sieve));
	sieve[1] = true;	// 1 is not prime
	for (long long n=2; n<MAX; n++) {
		if (!sieve[n]) {
			for (long long m=2*n; m<MAX; m+=n) {
				sieve[m] = true;
			}
		}
	}

	long long x=0;
	long long y=0;
	long long w=0;
	long long w2=square(1+2*w);

	for (long long n=1; n<MAX; n++) {
		while (is(x, y, w2)) {
			cout << w << ' ' << n << endl;
			w++;
			w2=square(1+2*w);
		}

		move(x, y);
	}

	delete[] sieve;

	return 0;
}