Kaninho với bài toán chia hết và giai thừa

Xem PDF

Điểm: 480 Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Tối đến, nhân trời trăng thanh gió mát, nhìn lên trời, \(Kaninho\) bỗng nảy ra một bài toán hay và muốn đố các bạn như sau:

  • Cho hai dãy số nguyên dương gồm \(n\) phần tử \(a_1,a_2,...,a_n\)\(b_1,b_2,...,b_n\).

Đặt \(M=a_1^{b_1}a_2^{b_2}...a_n^{b_n}\)

Yêu cầu: Tìm số nguyên dương \(x\) nhỏ nhất sao cho \(x!\) chia hết cho \(M\).

Input

  • Dòng thứ nhất chứa số \(t\) \((1\le t\le 50)\) - Thể hiện số testcase

  • \(t\) test tiếp theo, mỗi test có dạng như sau:

    • Dòng đầu tiên chứa số \(n(1\le n\le 100)\)

    • \(n\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(a_i\), \(b_i\) \((1\le a_i\le 100,1\le b_i\le 10^{13})\)

Output

  • Ứng với mỗi testcase, in ra đáp án cần tìm

Scoring

  • Subtask \(1\) (\(37.5\%\) số điểm): \(1\le n\le 10 ; 1\le a_i\le 10; 1 \le b_i \le 5\)

  • Subtask \(2\) (\(62.5\%\) số điểm): không có ràng buộc nào thêm.

Example

Test 1

Input
1
2
3 2
4 1
Output
6

Bình luận

Không có bình luận nào.