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\) và \(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

1
2
3 2
4 1

6