Обозначим за L(x, p) бесконечную последовательность таких целых чисел y, что gcd(p, y) = 1 и y > x (где gcd — наибольший общий делитель двух чисел), расположенных в порядке возрастания. Элементы L(x, p) пронумерованы, начиная с 1; например, 9, 13 и 15 — соответственно первый, второй и третий элементы L(7, 22).
Напишите программу, обрабатывающую t запросов. Каждый запрос задаётся тремя целыми числами x, p и k, а ответ на запрос — k-й элемент последовательности L(x, p).
Выходные данные
Выведите t чисел, где i-е число — ответ на i-й запрос.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
7 22 1
7 22 2
7 22 3
|
9
13
15
|
|
2
|
5
42 42 42
43 43 43
44 44 44
45 45 45
46 46 46
|
187
87
139
128
141
|