Giai thừa ~n! = 1.2.3...n~ là một phép tính thú vị mà không có cách nào tính ra giá trị của nó nhanh hơn một vòng lặp for. Đó là một trong những bài học vở lòng khi coder Đức Tài học được trên kênh dạy lập trình TL channel. Sau khi kết thúc buổi học, em Tài đã được anh admin của kênh giới thiệu 2 bài tập nhẹ nhàng như sau: với ~x~ là số nguyên dương, ký hiệu ~f(x) = 1!.2! ... x!~ là tích các giai thừa từ ~1!~ đến ~x!~. Bây giờ cho trước số nguyên dương ~n~, hãy trả lời cho các câu hỏi sau:

1. Số nguyên dương ~k~ nhỏ nhất sao cho ~f(k)~ chia hết cho ~n~.

2. Số nguyên dương ~k~ nhỏ nhất sao cho ~f(n)~ không chia hết cho ~k~.

Bạn Tài có thể giải bài toán với ~n \le 10~, nhưng kênh TL lại cho giới hạn lên đến ~10^{12}~ và cho đến ~100~ test cases, SOS, hãy giúp Tài nhé.

Input

Dòng đầu tiên gồm số nguyên dương ~t \le 100~ cho biết số test.

Mỗi dòng tiếp theo trong ~t~ dòng gồm một số nguyên dương duy nhất với ~1 \le n \le 10^{12}.~

Output

Ứng với mỗi dòng, hãy trả lời cho câu hỏi 1) và 2).

Sample input

1
3

Sample output

3 5

Giải thích: ta thấy ~f(1)=1, f(2)=2~ chưa đủ chia hết cho ~3~, còn ~f(3)=1.2.6 = 12~ thì chia hết cho ~3~ nên đáp số của câu hỏi thứ nhất là ~3~; còn với câu hỏi thứ hai, ta thấy ~f(3)=12~ vẫn chia hết cho ~4~ nhưng không chia hết cho ~5~ nên đáp số là ~5.~

Các subtask trong bài (đều có chung giới hạn ~t \le 100~):

• Subtask 1: 10% điểm ứng với ~n \le 10~.

• Subtask 2: 30% điểm ứng với ~10 < n \le 2023.~

• Subtask 3: 30% điểm ứng với ~2023 < n \le 10^7.~

• Subtask 4: 30% điểm ứng với ~10^7 < n \le 10^{12}.~