G. Список чисел
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Обозначим за 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 (1 ≤ t ≤ 30000) — количество запросов.

Далее следуют t строк. В i-й строке записаны три числа x, p и k для i-го запроса (1 ≤ x, p, k ≤ 106).

Выходные данные

Выведите t чисел, где i-е число — ответ на i-й запрос.

Примеры
Входные данные
3
7 22 1
7 22 2
7 22 3
Выходные данные
9
13
15
Входные данные
5
42 42 42
43 43 43
44 44 44
45 45 45
46 46 46
Выходные данные
187
87
139
128
141