Informática Avançado - Semana 73

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