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 ≤ t ≤ 30000 ) — the number of queries to process. Then t lines follow. i -th line contains three integers x , p and k for i -th query ( 1 ≤ x , p , k ≤ 10 6 ). Print t integers, where i -th integer is the answer to i -th query.