CF920G List Of Integers

Let's denote as $ L(x,p) $ an infinite sequence of integers $ y $ such that $ gcd(p,y)=1 $ and $ y>x $ (where $ gcd $ is the greatest common divisor of two integer numbers), sorted in ascending order. The elements of $ L(x,p) $ are $ 1 $ -indexed; for example, $ 9 $ , $ 13 $ and $ 15 $ are the first, the second and the third elements of $ L(7,22) $ , respectively. You have to process $ t $ queries. Each query is denoted by three integers $ x $ , $ p $ and $ k $ , and the answer to this query is $ k $ -th element of $ L(x,p) $ .

The first line contains one integer $ t $ ( $ 1

Print $ t $ integers, where $ i $ -th integer is the answer to $ i $ -th query.