Hôm nay, để giúp cả lớp ôn lại khái niệm về ước chung và bội chung, thầy giáo dạy toán của G và H đưa ra một thử thách nho nhỏ.

Thầy viết lên bảng hai cột số nguyên, mỗi cột gồm \(x\) số – cột bên trái là các số nguyên dương tăng dần bắt đầu từ \(a\), nghĩa là \(a, a + 1, a + 2, \dots, a + x - 1\), cột bên phải là các số nguyên dương tăng dần bắt đầu từ \(b\), nghĩa là \(b, b + 1, b + 2, \dots, b + x - 1\). Các số này được viết thành \(x\) hàng, hàng thứ \(i\) gồm hai số nguyên dương \(a + i - 1\) và \(b + i - 1\).

Sau đó, thầy chia cả lớp thành các nhóm nhỏ, mỗi nhóm cần tìm ra hàng mà bội chung nhỏ nhất của hai số trên hàng đó là nhỏ nhất và tính ra giá trị bội chung nhỏ nhất đó. Nhóm của G và H muốn giành chiến thắng trong trò chơi nên nhờ bạn giúp giải bài toán của thầy giao. Các bạn hãy giúp G và H nhé.

Input

• Dữ liệu đọc từ tệp văn bản LCM.inp:
  • Dòng đầu tiên gồm một số nguyên dương \(T\) (\(1 \le T \le 200\)) là số bộ số cần xử lý.
  • \(T\) dòng tiếp theo, mỗi dòng gồm ba số nguyên \(a, b, x\) (\(1 \le a, b, x \le 10^{14}\)).

Output

• Ghi ra tệp văn bản LCM.out:
  • Với mỗi bộ dữ liệu, in ra giá trị bội chung nhỏ nhất tìm được. Vì kết quả có thể rất lớn nên chỉ cần in ra phần dư khi chia cho \(10^9 + 7\).

Example

2
14 9 7
24 2 7

30
24

Scoring

• \(36\%\) số điểm có \(x \le 5000\).
• \(28\%\) số điểm khác có \(a, b, x \le 10^6\).
• \(18\%\) số điểm khác có \(a, b, x \le 10^{11}\).
• \(18\%\) số điểm còn lại không có giới hạn gì thêm.