Horrible Sequence

The length of a sequence <a_1, a_2, ..., a_k> of positive integers is the number of integers in the sequence, k. Given a positive integer M, consider the following two tasks.

• Task A: Among all sequences of positive integers whose sum satisfies a_1 + a_2 + ... + a_n = M, find those whose product a_1 × a_2 × ... × a_n is as large as possible. If optimal sequences with different lengths exist, find both the maximum and minimum possible values of the length n.
• Task B: Among all sequences of positive integers whose product satisfies a_1 × a_2 × ... × a_m = M, find those whose sum a_1 + a_2 + ... + a_m is as small as possible. If optimal sequences with different lengths exist, find both the maximum and minimum possible values of the length m.

Write a program that outputs the maximum and minimum possible lengths for task A, followed by the maximum and minimum possible lengths for task B.

The first line contains an integer M. (1 ≤ M ≤ 1,000,000)

Print four integers on one line, separated by spaces: the maximum possible length n for task A, the minimum possible length n for task A, the maximum possible length m for task B, and the minimum possible length m for task B, in that order.