Among all the factors of a positive integer N, there may exist several consecutive numbers. For example, 630 can be factored as 3×5×6×7, where 5, 6, and 7 are the three consecutive numbers. Now given any positive N, you are supposed to find the maximum number of consecutive factors, and list the smallest sequence of the consecutive factors.

Input Specification:

Each input file contains one test case, which gives the integer N (1<N<2^{31}).

Output Specification:

For each test case, print in the first line the maximum number of consecutive factors. Then in the second line, print the smallest sequence of the consecutive factors in the format factor[1]*factor[2]*...*factor[k], where the factors are listed in increasing order, and 1 is NOT included.

Sample Input:

630

Sample Output:

3
5*6*7

注意点

• N 不会被自己以为的大于 $\sqrt{N}$ 的多个连续整数整除，因此只需要从 2 ～ $\sqrt{N}$ 遍历连续整数的第一个。
• 如果遍历结束后 ansLen 依然为 0，说明不超过 $\sqrt{N}$ 的整数中不存在能整除 N 的连续整数，因此答案就是 N 本身。此时输出特例，即连续个数为 1，因数为 N 本身。
• 需要用 long long，防止中间乘积超过 int 导致溢出。

#include <cstdio>
#include <cmath>

int main() {
    long long n;
    scanf("%lld", &n);
    long long ansI, ansLen = 0, sqr = sqrt(1.0 * n);
    for (long long i = 2; i <= sqr; i++) {
        long long temp = 1;
        for (long long j = i; j <= n ; j++) {
            temp *= j;
            if (n % temp == 0) {
                if (j - i + 1 > ansLen) {
                    ansLen = j - i + 1;
                    ansI = i;
                }
            } else {
                break;
            }
        }
    }
    if (ansLen == 0) {
        printf("1\n%lld", n);
    } else {
        printf("%lld\n", ansLen);
        for (long long i = 0; i < ansLen; i++) {
            printf("%lld", ansI + i);
            if (i != ansLen - 1) {
                printf("*");
            }
        }
    }
    return 0;
}