Обозначим за 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).