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

Xem PDF

Điểm: 600 (p) Thời gian: 3.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

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 8 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 hai điều kiện :

  • \(d>a\).
  • Ước chung lớn nhất của \(d\)\(b\)\(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 \leq 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 \leq 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 đó.

Example

Test 1

Input
3
3 4 5
4 5 6
5 6 7 
Output
13
12
25
Note
  • Với bộ số \(3\) \(4\) \(5\) ta sẽ có dãy số sau : \(5\) \(7\) \(9\) \(11\) \(13\) \(15\) … Số lớn thứ \(5\) là số \(13\).

  • Với bộ số \(4\) \(5\) \(6\) ta sẽ có dãy số sau : \(6\) \(7\) \(8\) \(9\) \(11\) \(12\) \(13\) \(14\) \(\cdots\) Số lớn thứ \(6\) là số \(12\).

  • Với bộ số \(5\) \(6\) \(7\) ta sẽ có dãy số sau : \(7\) \(11\) \(13\) \(17\) \(19\) \(23\) \(25\) \(29\) \(31\) \(\cdots\) Số lớn thứ \(7\) là số \(25\).


Bình luận


  • 1
    huyhau6a2 5:50 p.m. 22 Tháng 2, 2022

    Dạo này hơi nhiều ngưòi ac bài này


    • 3
      huyhau6a2 1:57 p.m. 30 Tháng 11, 2021 đã chỉnh sửa

      Mình ac bài này rồi, ami chắc buồn lắm nhỉ. Hihihi! Mà công nhận admin ra đề nhìn vui thật, có hứng làm!

      1 phản hồi