#include <vector>
#include <bitset>
#include <iostream>
using namespace std;
const int N = 1024;
int GetRank(vector<bitset<N>> matrix) {
const int n = matrix.size();
int r = 0;
vector<bool> used(n);
for (int col = 0; col < n; ++col) {
int pivot = -1;
for (int row = 0; row < n; ++row) {
if (!used[row] && matrix[row][col]) {
pivot = row; break;
}
}
if (pivot == -1) { continue; }
used[pivot] = true;
++r;
for (int r = 0; r < n; ++r) {
if (r == pivot) { continue; }
if (matrix[r][col]) {
matrix[r] ^= matrix[pivot];
}
}
}
return r;
}
int main() {
int n;
cin >> n;
srand(time(NULL));
for (int i = 0; i < 40; ++i) {
int m = n + i;
vector<bitset<N>> matrix(m);
for (int i = 0; i < m; ++i) {
for (int j = 0; j < m; ++j) {
matrix[i][j] = rand() % 2;
}
}
cout << m << " "<< GetRank(matrix) << "\n";
}
}
I2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGUgPGJpdHNldD4KI2luY2x1ZGUgPGlvc3RyZWFtPgogCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiAKY29uc3QgaW50IE4gPSAxMDI0OwogCmludCBHZXRSYW5rKHZlY3RvcjxiaXRzZXQ8Tj4+IG1hdHJpeCkgewogIGNvbnN0IGludCBuID0gbWF0cml4LnNpemUoKTsKICBpbnQgciA9IDA7CiAgdmVjdG9yPGJvb2w+IHVzZWQobik7CiAKICBmb3IgKGludCBjb2wgPSAwOyBjb2wgPCBuOyArK2NvbCkgewogICAgaW50IHBpdm90ID0gLTE7CiAgICBmb3IgKGludCByb3cgPSAwOyByb3cgPCBuOyArK3JvdykgewogICAgICBpZiAoIXVzZWRbcm93XSAmJiBtYXRyaXhbcm93XVtjb2xdKSB7CiAgICAgICAgcGl2b3QgPSByb3c7IGJyZWFrOwogICAgICB9CiAgICB9CiAKICAgIGlmIChwaXZvdCA9PSAtMSkgeyBjb250aW51ZTsgfQogICAgdXNlZFtwaXZvdF0gPSB0cnVlOwogICAgKytyOwogCiAgICBmb3IgKGludCByID0gMDsgciA8IG47ICsrcikgewogICAgICBpZiAociA9PSBwaXZvdCkgeyBjb250aW51ZTsgfQogICAgICBpZiAobWF0cml4W3JdW2NvbF0pIHsKICAgICAgICBtYXRyaXhbcl0gXj0gbWF0cml4W3Bpdm90XTsKICAgICAgfQogICAgfQogIH0KICByZXR1cm4gcjsKfQogCmludCBtYWluKCkgewogIGludCBuOwogIGNpbiA+PiBuOwogCiAgc3JhbmQodGltZShOVUxMKSk7CiAKICBmb3IgKGludCBpID0gMDsgaSA8IDQwOyArK2kpIHsKICAgIGludCBtID0gbiArIGk7CiAgICB2ZWN0b3I8Yml0c2V0PE4+PiBtYXRyaXgobSk7CiAgICBmb3IgKGludCBpID0gMDsgaSA8IG07ICsraSkgewogICAgICBmb3IgKGludCBqID0gMDsgaiA8IG07ICsraikgewogICAgICAgIG1hdHJpeFtpXVtqXSA9IHJhbmQoKSAlIDI7CiAgICAgIH0KICAgIH0KIAogICAgY291dCA8PCBtIDw8ICIgIjw8IEdldFJhbmsobWF0cml4KSA8PCAiXG4iOwogIH0KfQo=