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

I2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGUgPGJpdHNldD4KI2luY2x1ZGUgPGlvc3RyZWFtPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmNvbnN0IGludCBOID0gMTAyNDsKCmludCBHZXRSYW5rKHZlY3RvcjxiaXRzZXQ8Tj4+IG1hdHJpeCkgewogICAgY29uc3QgaW50IG4gPSBtYXRyaXguc2l6ZSgpOwogICAgaW50IHIgPSAwOwogICAgdmVjdG9yPGJvb2w+IHVzZWQobik7CgogICAgZm9yIChpbnQgY29sID0gMDsgY29sIDwgbjsgKytjb2wpIHsKICAgICAgICBpbnQgcGl2b3QgPSAtMTsKICAgICAgICBmb3IgKGludCByb3cgPSAwOyByb3cgPCBuOyArK3JvdykgewogICAgICAgICAgICBpZiAoIXVzZWRbcm93XSAmJiBtYXRyaXhbcm93XVtjb2xdKSB7CiAgICAgICAgICAgICAgICBwaXZvdCA9IHJvdzsgYnJlYWs7CiAgICAgICAgICAgIH0KICAgICAgICB9CgogICAgICAgIGlmIChwaXZvdCA9PSAtMSkgeyBjb250aW51ZTsgfQogICAgICAgIHVzZWRbcGl2b3RdID0gdHJ1ZTsKICAgICAgICArK3I7CgogICAgICAgIGZvciAoaW50IHIgPSAwOyByIDwgbjsgKytyKSB7CiAgICAgICAgICAgIGlmIChyID09IHBpdm90KSB7IGNvbnRpbnVlOyB9CiAgICAgICAgICAgIGlmIChtYXRyaXhbcl1bY29sXSkgewogICAgICAgICAgICAgICAgbWF0cml4W3JdIF49IG1hdHJpeFtwaXZvdF07CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9CiAgICByZXR1cm4gcjsKfQoKdWludDY0X3QgeG9yc2hpZnQ2NCh1aW50NjRfdCogc3RhdGUpCnsKICAgIHVpbnQ2NF90IHggPSAqc3RhdGU7CiAgICB4Xj0geCA8PCAxMzsKICAgIHhePSB4ID4+IDc7CiAgICB4Xj0geCA8PCAxNzsKICAgICpzdGF0ZSA9IHg7CiAgICByZXR1cm4geDsKfQoKI2luY2x1ZGUgPHJhbmRvbT4KaW50IG1haW4oKSB7CiAgICBpbnQgbj05MDA7CgogICAgdWludDY0X3Qgc3RhdGUgPSB0aW1lKE5VTEwpOwogICAgZm9yIChpbnQgaSA9IDA7IGkgPCAxMDA7ICsraSkgewogICAgICAgIGludCBtID0gbiArIGk7CiAgICAgICAgdmVjdG9yPGJpdHNldDxOPj4gbWF0cml4KG0pOwogICAgICAgIGZvciAoaW50IGkgPSAwOyBpIDwgbTsgKytpKSB7CiAgICAgICAgICAgIGZvciAoaW50IGogPSAwOyBqIDwgbTsgKytqKSB7CiAgICAgICAgICAgICAgICBtYXRyaXhbaV1bal0gPSB4b3JzaGlmdDY0KCZzdGF0ZSkgJSAyOwogICAgICAgICAgICB9CiAgICAgICAgfQoKICAgICAgICBjb3V0IDw8IG0gPDwgIiAiPDwgR2V0UmFuayhtYXRyaXgpIDw8ICJcbiI7CiAgICB9Cn0K