#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>
#define N_MAX 1000001
int solns[N_MAX];
void initialize_solns() {
for (int i = 0; i < N_MAX; i++) {
solns[i] = 0;
}
solns[1] = 1;
solns[2] = 2;
solns[3] = 3;
solns[4] = 3;
// Actually solve
for (int i = 1; i < N_MAX; i++) {
if (!solns[i] || solns[i-1] + 1 < solns[i]) {
solns[i] = solns[i-1] + 1;
}
for (int j = 1; j <= i && j * i < N_MAX; j++) {
if (!solns[j*i] || solns[i] + 1 < solns[j*i]) {
solns[j*i] = solns[i] + 1;
}
}
}
}
int main() {
initialize_solns();
int Q;
for(int a0 = 0; a0 < Q; a0++){
int N;
}
return 0;
}
I2luY2x1ZGUgPG1hdGguaD4KI2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdHJpbmcuaD4KI2luY2x1ZGUgPHN0ZGxpYi5oPgojaW5jbHVkZSA8YXNzZXJ0Lmg+CiNpbmNsdWRlIDxsaW1pdHMuaD4KI2luY2x1ZGUgPHN0ZGJvb2wuaD4KCiNkZWZpbmUgTl9NQVggMTAwMDAwMQoKaW50IHNvbG5zW05fTUFYXTsKCnZvaWQgaW5pdGlhbGl6ZV9zb2xucygpIHsKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgTl9NQVg7IGkrKykgewogICAgICAgIHNvbG5zW2ldID0gMDsKICAgIH0KICAgIHNvbG5zWzFdID0gMTsKICAgIHNvbG5zWzJdID0gMjsKICAgIHNvbG5zWzNdID0gMzsKICAgIHNvbG5zWzRdID0gMzsKICAgIC8vIEFjdHVhbGx5IHNvbHZlCiAgICBmb3IgKGludCBpID0gMTsgaSA8IE5fTUFYOyBpKyspIHsKICAgICAgICBpZiAoIXNvbG5zW2ldIHx8IHNvbG5zW2ktMV0gKyAxIDwgc29sbnNbaV0pIHsKICAgICAgICAgICAgc29sbnNbaV0gPSBzb2xuc1tpLTFdICsgMTsKICAgICAgICB9CiAgICAgICAgZm9yIChpbnQgaiA9IDE7IGogPD0gaSAmJiBqICogaSA8IE5fTUFYOyBqKyspIHsKICAgICAgICAgICAgaWYgKCFzb2xuc1tqKmldIHx8IHNvbG5zW2ldICsgMSA8IHNvbG5zW2oqaV0pIHsKICAgICAgICAgICAgICAgIHNvbG5zW2oqaV0gPSBzb2xuc1tpXSArIDE7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9Cn0KCmludCBtYWluKCkgewogICAgaW5pdGlhbGl6ZV9zb2xucygpOwogICAgaW50IFE7IAogICAgc2NhbmYoIiVpIiwgJlEpOwogICAgZm9yKGludCBhMCA9IDA7IGEwIDwgUTsgYTArKyl7CiAgICAgICAgaW50IE47IAogICAgICAgIHNjYW5mKCIlaSIsICZOKTsKICAgICAgICBwcmludGYoIiVkXG4iLCBzb2xuc1tOXSk7CiAgICB9CiAgICByZXR1cm4gMDsKfQ==