Sau khi hay tin TN đi chơi với Tuấn, trái tim Ami tan vỡ. Chưa kịp vượt qua cú sốc này, lại nghe tin TN còn đi đêm với Blebleble, Ami sụp đổ hoàn toàn. Âu đây cũng là do số trời, khi số cặp (i,j) mà Ami tìm được là 0 :((. Nhưng Ami là một con người mạnh mẽ, cậu quyết không để TN và những mối tình tay ba oan nghiệt làm mình đau đớn. Cậu quyết định sang crush LN, một cô gái học LQĐ. Nhưng trớ trêu thay, có vẻ số tình lận đận vẫn không buông tha Ami khi LN đã là người trong mộng của ĐNLT. Tự nhủ anh em quan trọng hơn cả, cậu không tranh giành LN với ĐNLT nữa. Cậu chuyển sang một đối tượng mới hoàn toàn – LMH :)).

Lại nói LMH là cô bạn xinh xắn và vô cùng thông minh – đặc biệt trong môn tin học. Cô bé tự hứa không couple với những ai không code giỏi hơn mình. Vì thế bạn nữ đặt ra một tiêu chuẩn : những ai muốn LMH chấp nhận phải đưa ra một bài toán mà cô không thể giải được trong 1s !!!. Ami lại là người thích thử thách, sau bao nhiêu phút miệt mài, cậu đã nghĩ ra một bài toán hay ho và quyết định đem nó làm lễ vật tán tỉnh LMH. LMH, sau khi nghĩ trong 0.1s ban đầu, cô nhíu mày. 0.5s tiếp theo, cô đưa tay vỗ trán. 0.69s tiếp theo, cô lại dùng khăn thấm mồ hôi. 1s trôi qua, Ami mừng rỡ : “Thoát kiếp FA rồi :))”. Nhưng với bản tính thông minh của mình, LMH lại thách đố :”Nếu trong contest 9 lần này không bạn nào A/C được thì tớ sẽ chấp nhận cậu là người đầu tiên và duy nhất :v”. Vì vậy hôm nay, Ami xin hân hạnh mang đến cho các bạn bài toán này, hi vọng không ai A/C để cậu có thể khoe với mẹ rằng mình đã có bạn gái xinh đẹp như thế.

Bài toán cực kì ngắn gọn và đơn giản. Các bạn được cho 3 số a , b , c. Xét các số tự nhiên d từ 1 đến vô cùng, viết những số d thỏa mãn 2 điều kiện :

          *d > a.
          *Ước chung lớn nhất của d và b là 1.

thành một dãy số (tất nhiên dãy này cũng dài vô cùng). Các bạn hãy tìm số lớn thứ c của dãy số này.

Input

Dòng đầu là một số nguyên dương q (q <= 30000) là số bộ dữ liệu.
q dòng tiếp theo, mỗi dòng sẽ chứa 3 số nguyên dương a , b ,c là một bộ dữ liệu (a, b, c <= 1000000).

Output

Các bạn cần in ra q số, mỗi số tương ứng là 1 câu trả lời cho bộ dữ liệu đó.