Lista de Inteiros
Vamos definir como $$L(x, p)$$ uma sequência infinita de inteiros $$y$$ tais que $$gcd(p, y) = 1$$ e $$y > x$$ (onde gcd é o maior divisor comum entre os dois inteiros), ordenados em ordem crescente. Os elementos de $$L(x, p)$$ são indexados em 1. Por exemplo, 9, 13 e 15 são o primeiro, o segundo e o terceiro elementos de $$L(7, 22)$$, respectivamente.
Você deve processar $$n$$ perguntas. Cada pergunta é definida por três inteiros $$x$$, $$p$$ e $$k$$, e a resposta para cada pergunta é o $$k$$-ésimo elemento de $$L(x, p)$$.
Entrada
A primeira linha de entrada contém um inteiro $$t$$, o número de perguntas para processar.
Então, $$n$$ linhas seguem. A $$i$$-ésima linha contém três inteiros $$x$$, $$p$$ e $$k$$ que representam a $$i$$-ésima pergunta.
Saída
Imprima $$t$$ inteiros, onde o $$i$$-ésimo inteiro é a resposta para a $$i$$-ésima pergunta.
Restrições
- $$1 \leq t \leq 30000$$
- $$1 \leq x,p,k\leq 10^6$$
Exemplos
| ENTRADA | SAÍDA |
| 3 7 22 1 7 22 2 7 22 3 |
9 13 15 |
| ENTRADA | SAÍDA |
| 5 42 42 42 43 43 43 44 44 44 45 45 45 46 46 46 |
187 87 139 128 141 |
Enviar solução: codeforces