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 ≤ 10^6) — 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
9

Output
504

Input
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.

Difficulty: competition

Starter code:

Solutions:
def gcd(a, b):
    c = a % b
    return gcd(b, c) if c else b

s, a = 0, int(input())
if a < 3: print(a)
else:
    while a ** 3 > s:
        b = a - 1
        while a * b * b > s:
            if gcd(a, b) == 1:
                d = a * b
                c = b - 1
                while d * c > s:
                    if gcd(c, d) == 1: s = d * c
                    c -= 1
            b -= 1
        a -= 1
    print(s)

n = int(input())
res = n * (n - 1)
gcd = lambda a, b: b if a % b == 0 else gcd(b, a % b)

for i in range(n - 2 if n % 2 != 0 else n - 3, 0, -2):
    if gcd(n, i) == 1 and gcd(n - 1, i) == 1:
        res = res * i if n % 2 != 0 else max(res * i, int(res / 2) * (n - 2),
                (n - 1) * (n - 2) * (n - 3))
        break

if n < 3:
    res = n

print(res)


n = int(input())
gcd = lambda a, b: b if a % b == 0 else gcd(b, a % b)

if n % 2:
    res = n * (n - 1) * (n - 2)
else:
    for i in range(n - 3, 0, -2):
        if gcd(n, i) != 1 or gcd(n - 1, i) != 1:
            continue
        res = max(n * (n - 1) * i,
                int(n * (n - 1) / 2) * (n - 2),
                (n - 1) * (n - 2) * (n - 3))
        break

if n < 3:
    res = n

print(res)


from fractions import gcd
n=int(input())

ans=0
for i in range(n,max(0,n-101),-1):
    for j in range(i,max(0,n-101),-1):
        for k in range(j,max(0,n-101),-1):
            x=(i*j)//gcd(i,j)
            x=(x*k)//gcd(x,k)
            ans=max(ans,x)
print(ans)


def gcd(a, b):
	while a:
		b %= a
		a, b = b, a
	return b

def lcm(a, b):
	return a // gcd(a, b) * b

n = int(input())
ans = 0
for i in range(n, max(0, n - 100), -1):
	for j in range(i, max(0, i - 100), -1):
		cur = lcm(i, j)
		for k in range(j, max(0, j - 100), -1):
			ans = max(ans, lcm(cur, k))
print(ans)


def gcd(a,b):
    #print(a,b)
    if b==0:
        return a
    else:
        return gcd(b,a%b)

def main():
    mode="filee"
    if mode=="file":f=open("test.txt","r")

    if mode=="file":n=int(f.readline())
    else:n=int(input())
    if n==1:
        print("1")
        return
    if n==2:
        print("2")
        return
    if n==3:
        print("6")
        return
    if n==4:
        print("12")
        return
    i=n+1
    [a,b,c]=[1,1,1]
    stop=20
    while i>=n//2 and i>n-stop:
        i-=1
        j=n
        while j>=n//2-1 and j>n-stop:
            j-=1
            if i==j:continue
            k=n-1
            while k>=n//2-2 and k>n-stop:
                k-=1
                if k==j:continue
                if gcd(i,j)==1 and gcd(i,k)==1 and gcd(j,k)==1:
                    if (i*j*k) > (a*b*c):
                        [a,b,c]=[i,j,k]
                        #print(i,j,k)

    print(a*b*c)
    if mode=="file":f.close()


def __starting_point():
    main()

__starting_point()

n=int(input())
if(n<3):
    print(n)
elif(n%2==0):
    if(n%3==0 and (n-3)%3==0):
        print((n-1)*(n-2)*(n-3))
    else:
        print(n*(n-1)*(n-3))
else:
    print(n*(n-1)*(n-2))


n=int(input())
if(n<3):
    print(n)
elif(n%2==0):
    if(n%3==0 and (n-3)%3==0):
        print((n-1)*(n-2)*(n-3))
    else:
        print(n*(n-1)*(n-3))
else:
    print(n*(n-1)*(n-2))


def gcd(a,b):
    while b:
        a,b = b,a%b
    return a

def lcm(a,b):
    return a*b//gcd(a,b)

n = int(input())
if n==1:
    print(1)
elif n==2:
    print(2)
elif n%2 == 1:
    print(lcm(n,lcm(n-2,n-1)))
else :
    ans = 0
    for i in range(max(n-50,1),n+1) :
        for j in range(max(n-50,1),n+1) :
            for k in range(max(n-50,1),n+1) :
                ans = max(ans,lcm(i,lcm(j,k)))
    print(ans)

def main():
    n = int(input())
    print(n if n < 3 else ((n - 1) * (n * (n - 2) if n & 1 else (n - 3) * (n if n % 3 else n - 2))))


def __starting_point():
    main()

__starting_point()

n = int(input())
print(n if n < 3 else ((n - 1) * (n * (n - 2) if n & 1 else (n - 3) * (n if n % 3 else n - 2))))

n = int(input())
if n < 3: 
    print(n)
    return
if n % 2 != 0: 
    print(n*(n-1)*(n-2))
    return
if n % 3 == 0: 
    print((n - 3)* (n - 1) * (n - 2))
    return
print((n - 1) * (n) * (n - 3))


#!/usr/bin/env python3
import collections, itertools, functools, math, fractions
import operator

def lcm(a, b):
    return (a*b)//fractions.gcd(a, b)

def solve(n):
    if n <= 2:
        return n

    if n%2 == 1:
        return lcm(n, lcm(n-1, n-2))

    offset = 100
    if n-offset < 0:
        offset = n
    r = 1
    for i in range(n, n-offset, -1):
        for j in range(i, n-offset, -1):
            for k in range(j, n-offset, -1):
                r = max(r, lcm(i, lcm(j, k)))
    return r


def __starting_point():
    print(solve(int(input())))


__starting_point()

from fractions import gcd
g=lambda a,b:a//gcd(a,b)*b
n=int(input())+1
m=max(1,n-50)
print(max([g(a,g(b,c))for a in range(m,n)for b in range(m,n) for c in range(m,n)]))

'''
Created on May 4, 2016
@author: Md. Rezwanul Haque
'''
n = int (input())
if(n<3):print(n)
elif(n%2==0):
    if(n%3 == 0 and (n-3)%3 == 0):
        print((n-1)*(n-2)*(n-3))
    else:
        print(n*(n-1)*(n-3))
else:
    print(n*(n-1)*(n-2))


from fractions import gcd

n= int(input())

lim = 50
r = 0

if n <= 2 :
    print(n)
elif n == 3 :
    print(6)
else:
    i = n
    while i>0 and i>n-lim:
        j = i-1
        while j>0 and j>n-lim:
            k = j-1
            while k>0 and k>n-lim:
                x = (i*j)//gcd(i,j)
                x = (k*x)//gcd(k,x)
                r = max(r,x)
                k -= 1
            j -= 1
        i -=1
    print(r)

#!/usr/bin/env python3
def read_string():
    return input()
def read_strings(return_type = iter, split = None, skip = 0):
    return return_type(input().split(split)[skip:])
def read_lines(height, return_type = iter):
    return return_type(read_string() for i in range(height))
def read_number():
    return int(input())
def read_numbers(return_type = iter, skip = 0):
    return return_type(int(i) for i in input().split()[skip:])
def read_values(*types, array = None):
    line = input().split()
    result = []
    for return_type, i in zip(types, list(range(len(types)))):
        result.append(return_type(line[i]))
    if array != None:
        array_type, array_contained = array
        result.append(array_type(array_contained(i) for i in line[len(types):]))
    return result
def read_array(item_type = int, return_type = iter, skip = 0):
    return return_type(item_type(i) for i in input().split()[skip:])
def read_martix(height, **args):
    return_type = args["return_type"] if "return_type" in args else iter
    return_type_inner = args["return_type_inner"] if "return_type_inner" in args else return_type
    return_type_outer = args["return_type_outer"] if "return_type_outer" in args else return_type
    item_type = args["item_type"] if "item_type" in args else int
    return return_type_outer(read_array(item_type = item_type, return_type = return_type_inner) for i in range(height))
def read_martix_linear(width, skip = 0, item_type = int, skiped = None):
    num = read_array(item_type = item_type, skip = skip)
    height = len(num) / width
    return [num[i * width: (i + 1) * width] for i in range(height)]
def gcd(x, y):
    while x != 0:
        y %= x;
        if y == 0:
            return x;
        x %= y;
    return y;
def lcm(x, y):
    return x * y // gcd(x, y)
def main():
    n = read_number()
    r = list(range(max(1, n - 20), n+1))
    print(max([lcm(lcm(x,y),z) for x in r for y in r for z in r]))
def __starting_point():
    main()

__starting_point()

def gcd(x, y):
    if x: return gcd(y % x, x)
    return y
def lcm(x, y):
    return x * y // gcd(x, y)
n = int(input())
r = list(range(max(1, n - 20), n+1))
print(max([lcm(lcm(x,y),z) for x in r for y in r for z in r]))