Sau khi học xong bài về phép chia hết, thầy có ra cho lớp ~t~ câu đố, mỗi câu đố bao gồm:

• Cho 3 số nguyên dương ~a, b~ và ~n~.

• Hãy tìm số nguyên dương ~m~ nhỏ nhất thỏa mãn ~m \ge n~, ~m~ chia hết cho ~a~ và ~m~ không chia hết cho ~b~. Nếu không có số nguyên nào thỏa mãn thì ~m = -1~.

Dữ liệu

• Dòng đầu tiên gồm số nguyên dương ~t~ ~(t \le 10^5)~.

• ~t~ dòng tiếp theo, dòng thứ ~i~ chứa 3 số nguyên dương ~a_i, b_i~ và ~n_i~ (~a_i, b_i \le 10^9~; ~n_i \le 10^{18}~).

Kết quả

• In ra ~t~ dòng, dòng thứ ~i~ là số ~m_i~ tìm được cho câu đố thứ ~i~.

Ví dụ

Sample Input 1

2
2 3 7
8 4 2

Sample Output 1

8
-1

Sample Input 2

3
3 2 1
4 6 9
10 25 82

Sample Output 2

3
16
90