Mọi số tự nhiên lớn hơn \(1\) có thể viết một cách duy nhất (không kể sự sai khác về thứ tự các thừa số) thành tích các thừa số nguyên tố. Trong bài toán này, chúng ta sẽ quan tâm đến các cách biểu diễn (có tính đến thứ tự) của một số thành tích các thừa số nguyên tố. Ví dụ:

• \(10 = 2 \cdot 5 = 5 \cdot 2\)
• \(20 = 2 \cdot 2 \cdot 5 = 2 \cdot 5 \cdot 2 = 5 \cdot 2 \cdot 2\)

Gọi \(f(k)\) là số cách biểu diễn \(k\) thành tích các thừa số nguyên tố có tính đến thứ tự các thừa số. Như vậy, \(f(10) = 2; f(20) = 3\).

Yêu cầu: Cho số nguyên dương \(n\), tìm số \(k\) nhỏ nhất mà \(f(k) = n\).

Input

• Gồm nhiều bộ dữ liệu, mỗi bộ trên một dòng chứa một số nguyên \(n\) (\(n < 2^{63}\)).
• Dữ liệu đảm bảo, với mỗi giá trị \(n\) tồn tại ít nhất một giá trị \(k\) không vượt quá \(2^{63}-1\) thỏa mãn.

Output

• Với mỗi bộ dữ liệu, ghi ra một dòng gồm \(2\) số \(n, k\) mà \(f(k) = n\).

Example

1
2
3
105

1 2
2 6
3 12
105 720

Nguồn: Bài tập thầy Đỗ Đức Đông năm 2019