Vào năm 2027, Chiến dịch Giám sát Không gian số Quốc gia vận hành chuỗi Vệ tinh quỹ đạo tầm thấp "VNASAT-2027". Trong một đợt truyền dữ liệu tọa độ định vị quan trọng về Trạm Kiểm soát Mặt đất, hệ thống ghi nhận một đoạn dữ liệu mã hóa số học cực kỳ lớn.

Theo giao thức bảo mật của Vệ tinh năm 2027, khóa giải mã chính là kích thước khối dữ liệu ~n!~ (~n~ giai thừa). Do băng thông truyền tải dải hẹp bị nhiễu, trạm kiểm soát không nhận được trực tiếp giá trị ~n~ mà chỉ thu thập được chỉ số nền năng lượng bao gồm hai số nguyên dương ~a~ và ~k~. Nhờ tài liệu kỹ thuật của dự án, các kỹ sư biết rằng ~n~ chính là số nguyên không âm nhỏ nhất sao cho dung lượng khối giai thừa ~n!~ chia hết cho ~a^k~ (~n! : a^k~).

Vì trong một chu kỳ truyền dữ liệu có tới ~T = 10^6~ truy vấn mã hóa từ nhiều Vệ tinh gửi về đồng thời, việc tính toán thủ công hay áp dụng thuật toán duyệt thông thường sẽ dẫn đến quá thời gian đáp ứng (Time Limit Exceeded) của hệ thống không gian số.

Yêu cầu: Hãy lập trình giúp Trạm Kiểm soát Mặt đất xác định giá trị ~n~ nhỏ nhất cho từng truy vấn để khôi phục hoàn toàn khóa giải mã và giải mã thành công tọa độ Vệ tinh trước khi tín hiệu bị gián đoạn.

Input

• Dòng đầu tiên chứa số nguyên dương ~T~ (~T \le 10^6~) — số lượng truy vấn giải mã từ hệ thống Vệ tinh.

• ~T~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~a, k~ (~a, k \le 10^6~) cách nhau bởi dấu cách.

Output

• Ứng với mỗi truy vấn, in ra giá trị số nguyên ~n~ nhỏ nhất tìm được trên một dòng riêng biệt.

Scoring

Sample Input 1

3
8 3
40 5
999983 1000000

Sample Output 1

12
25
999982000017