A. LCM Challenge

A. LCM Challenge

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Some days ago, I learned the concept of LCM (least common multiple). I've played with it for several times and I want to make a big number with it.

But I also don't want to use many numbers, so I'll choose three positive integers (they don't have to be distinct) which are not greater than n. Can you help me to find the maximum possible least common multiple of these three integers?

Input

The first line contains an integer n (1 ≤ n ≤ 106) — the n mentioned in the statement.

Output

Print a single integer — the maximum possible LCM of three not necessarily distinct positive integers that are not greater than n.

Examples

input

Copy

9

output

504

input

Copy

7

output

210

Note

The least common multiple of some positive integers is the least positive integer which is multiple for each of them.

The result may become very large, 32-bit integer won't be enough. So using 64-bit integers is recommended.

For the last example, we can chose numbers 7, 6, 5 and the LCM of them is 7·6·5 = 210. It is the maximum value we can get.

题意：输入n，选择不大于n的三个数的最小公倍数的乘积最大（感觉有点像绕口令啊）。
题解：分类讨论 模拟      要使三个数最小公倍数最大，这三个数一定不能相同，也不能有公因子，比如9,选择9 9 9，最小公倍数就是9，相等于只有一个数，9 8 6的话9,6有公因子，没有9 8 7的最小公倍数大。 分类讨论样例是奇数，最大的n*n-1*n-2，偶数的话，手写n=6， 8， 12三种情况，选择三个数，使他们最小公倍数最大，会发现规律，n是3
的倍数的话，选择的三个数(n-1)*(n-2)*(n-3），然后其余就是8的这种情况，选择三个数n*(n-1)*(n-3)。

综合上述：选择的三个数，一定不相同，没有公因子。然后偶数判断n是都是3的倍数，选择三个数。

#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long n;
    cin>>n;
    if(n<3)
        cout<<n<<endl;
    else
    {
        if(n&1)
            cout<<n*(n-1)*(n-2)<<endl;
        else
        {
            if(n%3==0)
                cout<<(n-1)*(n-2)*(n-3)<<endl;
            else cout<<n*(n-1)*(n-3)<<endl;
        }
    }
    return 0;
}