Với mỗi số nguyên dương ~x~, ta định nghĩa ~\sigma(x)~ là số ước số nguyên dương của ~x~.

Yêu cầu: Cho số nguyên dương ~n~, hãy cho biết trong phạm vi từ 1 tới ~n~, số ~x~ có ~\sigma(x)~ lớn nhất là số nào? Trong trường hợp có nhiều số mà ~\sigma(x)~ đều là lớn nhất, hãy chỉ ra số ~x~ nhỏ nhất trong đó.

Input

• Dòng 1 chứa số nguyên dương ~T \le 10^5~ là số test.
• ~T~ dòng tiếp theo, mỗi dòng chứa số nguyên dương ~n \le 10^{18}~ ứng với một test.

Output

• Ứng với mỗi test ghi ra trên một dòng giá trị số ~x~ tìm được và giá trị ~\sigma(x)~ cách nhau bởi dấu cách.

Sample Input 1

5
12
122
7557
123456789
987654321

Sample Output 1

12 6
120 16
5040 60
122522400 864
735134400 1344