#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;
}

uint64_t xorshift64(uint64_t* state)
{
    uint64_t x = *state;
    x^= x << 13;
    x^= x >> 7;
    x^= x << 17;
    *state = x;
    return x;
}

#include <random>
int main() {
    int n=900;

    uint64_t state = time(NULL);
    for (int i = 0; i < 100; ++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] = xorshift64(&state) % 2;
            }
        }

        cout << m << " "<< GetRank(matrix) << "\n";
    }
}