#include <cstring>
#include <iostream>
#include <unordered_set>
#include <utility>

constexpr int maxn = 64;
unsigned long long mask[maxn];	// A087207 mask of prime factors
bool visited[maxn];

int S[maxn];

struct pair_hash {
    inline std::size_t operator()(const std::pair<int, unsigned long long> & v) const {
        return v.second;
    }
};

struct layer {
	int maxv = 0;

	std::unordered_set<std::pair<int, unsigned long long>, pair_hash> blocks[1+maxn][1+maxn];

	void add(int i, int j, int v, unsigned long long m) {
		if (maxv < v) {
			maxv = v;
		}

		blocks[i][j].insert(std::make_pair(v, m));
	}

	size_t size() const {
		size_t s = 0;

		for (int i = 1; i <= maxn; i++) {
			for (int j = 1; j <= maxn; j++) {
				s += blocks[i][j].size();
			}
		}

		return s;
	}
};

layer bottom;

// n: maximum k
// s: current term S[k]
// m: mask of prime factors that are mandatory in S[k+1]
// f: mask of prime factors that are forbidden in S[k+1]
// k: current index
void explore_blocks(int n, int s, unsigned long long m, unsigned long long f, int k) {
	S[k] = s;

	if (m==0) {
		// this is a new block.
		// a block is characterized by:
		// - its endpoints,
		// - its values.

		unsigned long long mask_of_values = 0;
		for (int i = 1; i <= k; i++) {
			mask_of_values |= 1LL << (S[i]-1);
		}

		bottom.add(S[1], S[k], k, mask_of_values);
	} else {
		visited[s] = true;

		for (int z = 1; z <= n; z++) {
			if (!visited[z] && (mask[z] & m)==m && (mask[z] & f)==0) {
				explore_blocks(n, z, mask[z]-m, m, k+1);
			}
		}

		visited[s] = false;
	}
}

void explore_blocks(int n) {
	for (int s = 1; s <= n; s++) {
		explore_blocks(n, s, mask[s], 0, 1);
	}
}

int maxv;

void grow(const layer& middle) {
	layer *xtop = new layer;
	layer &top = *xtop;

	for (int i = 1; i <= maxn; i++) {
		for (int j = 1; j <= maxn; j++) {
			if (bottom.blocks[i][j].size()) {
				for (int k = 1; k <= maxn; k++) {
					if ((mask[j] & mask[k])==0) {
						for (int l = 1; l <= maxn; l++) {
							for (const auto & b : bottom.blocks[i][j]) {
								for (const auto & m : middle.blocks[k][l]) {
									if ((b.second & m.second)==0) {
										top.add(i, l, b.first + m.first, b.second + m.second);
									}
								}
							}
						}
					}
				}
			}
		}
	}

	if (top.maxv) {
		if (maxv < top.maxv) {
			maxv = top.maxv;
		}

		grow(top);
	}

	delete xtop;
}

int a(int n) {
	maxv = bottom.maxv;

	grow(bottom);

	return maxv;
}

int main() {
	std::memset(mask, 0, sizeof(mask));
	std::memset(visited, 0, sizeof(visited));

	unsigned long long b = 1;
	int v = 0;	// last value

	for (int n = 1; n<maxn; n++) {
		bool is_prime = false;

		if (n > 1 && !mask[n]) {
			is_prime = true;
			if (!b) {
				std::cerr << "# bug" << std::endl;
				return 1;
			}

			for (int m = n; m < maxn; m += n) {
				mask[m] += b;
			}

			b *= 2;
		}

		if (!is_prime) {
			explore_blocks(n);
			v = a(n);
		}
		std::cout << n << ' ' << v << std::endl;
	}

	return 0;
}