#include <cstdio>
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <string>
#include <memory.h>
#include <sstream>
#include <ctime>
#include <bitset>
using namespace std;

#pragma comment(linker, "/stack:64000000")

static const int N = 1000;
static const int M = 500;

bitset<N> nextRandString()
{
	bitset<N> result;
	for(int i = 0; i < N; i++)
		result[i] = (rand() % 2);
	return result;
}

bitset<N> nextRandSample()
{
	bitset<N> result;
	for(int i = 0; i < N; i++)
		result[i] = (rand() % 4 ? 0 : 1);
	return result;
}

bool match(const bitset<N> &b1, const bitset<N> &b2)
{
	bitset<N> b3 = b1 ^ b2;
	int k = b3.count();
	return (k == N / 2) || (k == N);
}

int main()
{
	srand(42);
	bitset<N> known;
	vector<bitset<N>> samples;
	vector<int> bcnt(N, 0);

	int dbg_known_checks = 0;

	for (int i = 0; i < M; i++)
	{
		bitset<N> current = nextRandString();
		samples.push_back(current);
		for (int j = 0; j < N; j++)
			bcnt[j] += current[j];
		if (!(match(current, known)))
			continue;

		bitset<N> modificator;
		for (int j = 0; j < N; j++)
			modificator[j] = ((bcnt[j] < i / 2) ? 0 : 1);

		while (1)
		{
			known = nextRandSample() ^ modificator;
			++dbg_known_checks;
			bool ok = true;
			for (int j = 0; j <= i; j++)
				if (match(known, samples[j]))
				{
					ok = false;
					break;
				}
			if (ok)
				break;
		}
	}
	cout << dbg_known_checks;
}