#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N, P[20], res[20][20], dist[20][20], cnt; vector<int>G[20];
bool used[20], iscenter[20], iscenterpass[20][20];
void init() {
for (int i = 0; i < 20; i++) {
for (int j = 0; j < 20; j++) {
res[i][j] = 0; dist[i][j] = 0; iscenterpass[i][j] = false; cnt = 0;
}
G[i].clear(); used[i] = false; iscenter[i] = false;
}
}
void dfs(int pos) {
cnt++;
for (int i = 0; i < G[pos].size(); i++) {
if (used[G[pos][i]] == true) continue;
used[G[pos][i]] = true;
dfs(G[pos][i]);
used[G[pos][i]] = false;
}
}
void dfs2(int pos, int root, bool flag) {
used[pos] = true; iscenterpass[root][pos] = flag;
for (int i = 0; i < G[pos].size(); i++) {
if (used[G[pos][i]] == true) continue;
bool E = (flag | iscenter[G[pos][i]]);
dfs2(G[pos][i], root, E);
}
}
int count_simple_path() {
cnt = 0;
for (int i = 1; i <= N; i++) {
used[i] = true; dfs(i); used[i] = false; cnt--;
}
return cnt / 2;
}
void dfs1(int pos, int root, int dep) {
if (dist[root][pos] != (1 << 30)) return;
dist[root][pos] = dep;
for (int i = 0; i < G[pos].size(); i++) dfs1(G[pos][i], root, dep + 1);
}
vector<int> get_center() {
for (int i = 1; i <= N; i++) G[i].clear();
for (int i = 2; i <= N; i++) { G[P[i]].push_back(i); G[i].push_back(P[i]); }
for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) dist[i][j] = (1 << 30); }
for (int i = 1; i <= N; i++) dfs1(i, i, 0);
int minx = (1 << 30);
for (int i = 1; i <= N; i++) {
int rem = 0;
for (int j = 1; j <= N; j++) rem = max(rem, dist[i][j]);
minx = min(minx, rem);
}
vector<int>vec;
for (int i = 1; i <= N; i++) {
int rem = 0;
for (int j = 1; j <= N; j++) rem = max(rem, dist[i][j]);
if (rem == minx) vec.push_back(i);
}
return vec;
}
pair<int, int> solve() {
vector<int> centroid = get_center(); for (int i = 0; i < centroid.size(); i++) iscenter[centroid[i]] = true;
for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) used[j] = false; dfs2(i, i, iscenter[i]); }
int maxn = 0, maxn2 = 0;
for (int i = 1; i <= N; i++) {
for (int j = i + 1; j <= N; j++) {
for (int k = 0; k <= N; k++) G[k].clear();
for (int k = 2; k <= N; k++) { G[P[k]].push_back(k); G[k].push_back(P[k]); }
G[i].push_back(j); G[j].push_back(i);
res[i][j] = count_simple_path();
res[j][i] = res[i][j];
maxn = max(maxn, res[i][j]);
if (iscenterpass[i][j] == true) maxn2 = max(maxn2, res[i][j]);
}
}
return make_pair(maxn, maxn2);
}
int cntv = 0, cntw = 0;
void dfs_solve(int dep) {
if (dep == N + 1) {
init(); cntw++;
pair<int, int> E = solve();
if (E.first != E.second) {
cntv++;
cout << "Case " << cntv << ":" << endl;
cout << N << endl;
for (int j = 2; j <= N; j++) cout << P[j] << " " << j << endl;
cout << endl;
}
return;
}
for (int j = 1; j < dep; j++) {
P[dep] = j;
dfs_solve(dep + 1);
}
}
int main() {
cin >> N;
dfs_solve(2);
cout << cntv << " out of " << cntw << " cases were counter-example" << endl;
return 0;
}