Dãy số nguyên tố cùng nhau

Với hai số nguyên dương $x$ và $p$, ký hiệu $L(x,p)$ là dãy vô hạn gồm tất cả các số nguyên $y$ thoả mãn đồng thời:

• $y>x$;
• $gcd(y,p)=1$.

Các phần tử của $L(x,p)$ được sắp xếp tăng dần và được đánh số bắt đầu từ $1$. Ví dụ, ba phần tử đầu tiên của $L(7,22)$ lần lượt là $9$, $13$ và $15$.

Cho $t$ truy vấn, mỗi truy vấn gồm ba số $x$, $p$, $k$. Với mỗi truy vấn, hãy tìm phần tử thứ $k$ của dãy $L(x,p)$.

Dữ liệu vào

• Dòng đầu chứa số nguyên $t$: số lượng truy vấn.
• $t$ dòng tiếp theo, dòng thứ $i$ chứa ba số nguyên $x$, $p$, $k$ mô tả truy vấn thứ $i$.

Dữ liệu ra

In ra $t$ dòng, dòng thứ $i$ là đáp án của truy vấn thứ $i$.

Ràng buộc

• $1\le t\le 30000$
• $1\le x,p,k\le {10}^6$

Ví dụ