Quase Primos Malucos

Nina é uma esperta garota que adora fazer contas. Recentemente Nina pensou em um joguinho muito interessante a qual chamou de Quase Primos Malucos.

A ideia do problema dos quase primos malucos que é um número não pode ser primo, no entanto todos os divisores (além de $1$ ) devem ser maiores que $10$ e devem haver mais de $10$ divisores. Também é importante perceber que os divisores devem ser menores que a raiz quadrada do número quase primo maluco.

A brincadeira de Nina consiste em falar um número qualquer e a outra pessoa ter que responder o menor número quase primo maluco estritamente maior que o número dito.

Por exemplo:

Se Nina gritar $1$ , a resposta deve ser $508079$ , pois é o menor número maior que $1$ que não é primo e possui ao menos 10 divisores maiores que $10$ , que são: 11 13 17 19 121 143 187 209 221 247 323. E o mesmo ocorre para todos os números entre $1$ e $508079$ .

Para $600000$ o menor quase primo maluco é 600457, com os divisores 11 13 17 19 143 169 187 209 221 247 323.

O Número $26741$ não é um número quase primo maluco pois os seus divisores são 1 11 13 17 121 143 187 221 1573 2057 2431 e sua raiz quadrada é $163,5$ , logo todos os divisores maiores que $163$ devem ser desconsiderados.

Nina percebeu que sua brincadeira é difícil, pois os números quase primos malucos são muito grandes. No entanto ela gostaria de saber de antemão vários números quase primos e pediu a sua ajuda para escrever um programa que seja capaz de responder as questões para ela.

Entrada

A primeira linha contém o inteiro $T$ ( $1 \leq T \leq 1000$ ), que representa a quantidade de casos de teste.

Cada uma das próximas $T$ linhas contém um número $n$ ( $1 \leq n \leq 10^9$ ).

Saída

Para cada caso de teste, imprima uma linha contento o menor número quase primo maluco que seja estritamente maior que $n$ .

TAREFA

Você já deve ter percebido que esse problema talvez seja melhor ser implementado utilizando threads. Mas tome Cuidado! Você deve imprimir a resposta na ordem relativa a entrada. Ou seja, a resposta nunca pode ser diferente da mostrada nos exemplos abaixo.

Uma proposta para resolver o problema com threads, segue em pseudo-código abaixo:

struct parametro_thread
{
  int n;
  int tid;
  int result;
};
int main(void)
{
  leia(QUANTIDADE_DE_CASOS) //só para jogar fora mesmo
  while(1)
  {
    if(leia(n)== EOF) break;
    struct parametro_thread PARAMETRO_A.n=n;
    cria_thread(calcule_sequaseprimo_maluco(PARAMETRO_A))

    if(leia(n)== EOF) break;
    struct parametro_thread PARAMETRO_B.n=n;
    cria_thread(calcule_sequaseprimo_maluco(PARAMETRO_B))

    espera_thread1();
    espera_thread2();
    imprime(PARAMETRO_A.result);
    imprime(PARAMETRO_B.result);

  }
}

o pseudo-código acima possui um problema quando a entrada é ímpar! Tome cuidado.
o pseudo-código ilustrado acima é somente um exemplo e pode ser melhorado!
Use no máximo 2 threads (além da principal) pois o juiz disponibilizará apenas 2 núcleos de processamento.

Exemplos

Exemplo de entrada

2
550794
6530430

Exemplo de saída

600457
6533033

Exemplo de entrada

Exemplo de saída

Exemplo de entrada

Exemplo de saída

Exemplo de entrada

Exemplo de saída