#include <utility>
#include <vector>
std::vector< std::pair<int, int> > factor_table;
void fill_sieve( int n )
{
factor_table.resize(n+1);
for( int i = 1; i <= n; ++i ) {
if (i & 1)
factor_table[i] = std::pair<int, int>(i, 1);
else
factor_table[i] = std::pair<int, int>(2, i>>1);
}
for( int j = 3, j2 = 9; j2 <= n; ) {
if (factor_table[j].second == 1) {
int i = j;
int ij = j2;
while (ij <= n) {
factor_table[ij] = std::pair<int, int>(j, i);
++i;
ij += j;
}
}
j2 += (j + 1) << 2;
j += 2;
}
}
std::vector<int> factor( int num )
{
std::vector<int> factors;
factors.reserve(30);
do {
factors.push_back(factor_table[num].first);
num = factor_table[num].second;
} while (num != 1);
return factors;
}
const unsigned MAX = 10000000;
int main()
{
fill_sieve(MAX);
std::vector<int> factors;
for (int k = 1; k < MAX; k++) {
factor(k).swap(factors);
}
}
I2luY2x1ZGUgPHV0aWxpdHk+CiNpbmNsdWRlIDx2ZWN0b3I+CgpzdGQ6OnZlY3Rvcjwgc3RkOjpwYWlyPGludCwgaW50PiA+IGZhY3Rvcl90YWJsZTsKdm9pZCBmaWxsX3NpZXZlKCBpbnQgbiApCnsKICAgIGZhY3Rvcl90YWJsZS5yZXNpemUobisxKTsKICAgIGZvciggaW50IGkgPSAxOyBpIDw9IG47ICsraSApIHsKICAgICAgICBpZiAoaSAmIDEpCiAgICAgICAgICAgIGZhY3Rvcl90YWJsZVtpXSA9IHN0ZDo6cGFpcjxpbnQsIGludD4oaSwgMSk7CiAgICAgICAgZWxzZQogICAgICAgICAgICBmYWN0b3JfdGFibGVbaV0gPSBzdGQ6OnBhaXI8aW50LCBpbnQ+KDIsIGk+PjEpOwogICAgfQogICAgZm9yKCBpbnQgaiA9IDMsIGoyID0gOTsgajIgPD0gbjsgKSB7CiAgICAgICAgaWYgKGZhY3Rvcl90YWJsZVtqXS5zZWNvbmQgPT0gMSkgewogICAgICAgICAgICBpbnQgaSA9IGo7CiAgICAgICAgICAgIGludCBpaiA9IGoyOwogICAgICAgICAgICB3aGlsZSAoaWogPD0gbikgewogICAgICAgICAgICAgICAgZmFjdG9yX3RhYmxlW2lqXSA9IHN0ZDo6cGFpcjxpbnQsIGludD4oaiwgaSk7CiAgICAgICAgICAgICAgICArK2k7CiAgICAgICAgICAgICAgICBpaiArPSBqOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIGoyICs9IChqICsgMSkgPDwgMjsKICAgICAgICBqICs9IDI7CiAgICB9Cn0KCnN0ZDo6dmVjdG9yPGludD4gZmFjdG9yKCBpbnQgbnVtICkKewogICAgc3RkOjp2ZWN0b3I8aW50PiBmYWN0b3JzOwogICAgZmFjdG9ycy5yZXNlcnZlKDMwKTsKICAgIGRvIHsKICAgICAgICBmYWN0b3JzLnB1c2hfYmFjayhmYWN0b3JfdGFibGVbbnVtXS5maXJzdCk7CiAgICAgICAgbnVtID0gZmFjdG9yX3RhYmxlW251bV0uc2Vjb25kOwogICAgfSB3aGlsZSAobnVtICE9IDEpOwogICAgcmV0dXJuIGZhY3RvcnM7Cn0KCmNvbnN0IHVuc2lnbmVkIE1BWCA9IDEwMDAwMDAwOwoKaW50IG1haW4oKQp7CiAgICBmaWxsX3NpZXZlKE1BWCk7CgogICAgc3RkOjp2ZWN0b3I8aW50PiBmYWN0b3JzOwogICAgZm9yIChpbnQgayA9IDE7IGsgPCBNQVg7IGsrKykgewogICAgICAgIGZhY3RvcihrKS5zd2FwKGZhY3RvcnMpOwogICAgfQp9