#include <iostream>
#include <set>
#include <vector>
using namespace std;
 
set<int> expand(const set<int> &current, const vector<int> &primes, int limit) {
	set<int> res(current.begin(), current.end());
	for (auto n : current) {
		for (auto p : primes) {
			int x = n*p;
			if (x < limit) {
				res.insert(x);
			}
		}
	}
	return res;
}
 
int main() {
	vector<int> primes = { 2, 3, 5, 7 };
	set<int> s;
	s.insert(1);
	int target = 5917;
	int best = 2*5917;
	int i = 1;
	for (;;) {
		set<int> next = expand(s, primes, best);
		if (next.size() == s.size()) {
			break;
		}
		cout << "Generation " << i++ << ", best = " << best << endl;
		for (auto n : next) {
			if (n >= target && n < best) {
				best = n;
			}
		}
		s = next;
	}
	cout << "Best match: " << best << endl;
	return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8c2V0PgojaW5jbHVkZSA8dmVjdG9yPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKc2V0PGludD4gZXhwYW5kKGNvbnN0IHNldDxpbnQ+ICZjdXJyZW50LCBjb25zdCB2ZWN0b3I8aW50PiAmcHJpbWVzLCBpbnQgbGltaXQpIHsKCXNldDxpbnQ+IHJlcyhjdXJyZW50LmJlZ2luKCksIGN1cnJlbnQuZW5kKCkpOwoJZm9yIChhdXRvIG4gOiBjdXJyZW50KSB7CgkJZm9yIChhdXRvIHAgOiBwcmltZXMpIHsKCQkJaW50IHggPSBuKnA7CgkJCWlmICh4IDwgbGltaXQpIHsKCQkJCXJlcy5pbnNlcnQoeCk7CgkJCX0KCQl9Cgl9CglyZXR1cm4gcmVzOwp9CgppbnQgbWFpbigpIHsKCXZlY3RvcjxpbnQ+IHByaW1lcyA9IHsgMiwgMywgNSwgNyB9OwoJc2V0PGludD4gczsKCXMuaW5zZXJ0KDEpOwoJaW50IHRhcmdldCA9IDU5MTc7CglpbnQgYmVzdCA9IDIqNTkxNzsKCWludCBpID0gMTsKCWZvciAoOzspIHsKCQlzZXQ8aW50PiBuZXh0ID0gZXhwYW5kKHMsIHByaW1lcywgYmVzdCk7CgkJaWYgKG5leHQuc2l6ZSgpID09IHMuc2l6ZSgpKSB7CgkJCWJyZWFrOwoJCX0KCQljb3V0IDw8ICJHZW5lcmF0aW9uICIgPDwgaSsrIDw8ICIsIGJlc3QgPSAiIDw8IGJlc3QgPDwgZW5kbDsKCQlmb3IgKGF1dG8gbiA6IG5leHQpIHsKCQkJaWYgKG4gPj0gdGFyZ2V0ICYmIG4gPCBiZXN0KSB7CgkJCQliZXN0ID0gbjsKCQkJfQoJCX0KCQlzID0gbmV4dDsKCX0KCWNvdXQgPDwgIkJlc3QgbWF0Y2g6ICIgPDwgYmVzdCA8PCBlbmRsOwoJcmV0dXJuIDA7Cn0=