路径

时间限制:1s

空间限制:64MB

题目描述

某国有\(n\)个城市，编号分别为\(1,2,..,n\)

编号之差的绝对值小于等于\(21\)的两个城市\(a,b\)之间有交通道路连接，长度为\(lcm(a,b)\)，即它们的城市编号的最小公倍数。例如：城市\(6,8\)之间有一条长为\(24\)的交通道路连接，城市\(1,22\)之间有一条长为\(22\)的交通道路连接，而城市\(48,96\)之间没有交通道路连接。

使用交通道路从城市\(1\)到城市\(n\)，最短路径是多少？

参考公式: \(lcm(a,b) = a*b / gcd(a,b)\) ，其中\(lcm(a,b)\)表示两个数的最小公倍数， \(gcd(a,b)\) 表示两个数的最大公约数。

输入格式

第一行一个正整数\(n\)，表示城市的数量

输出格式

一个正整数，表示最短路径的长度。

样例输入1

23

样例输出1

48

样例1解释

\(1\to 23\)没有直接的路径，但是\(1\to 2\)的路径长度为\(2\)， \(2\to 23\)的路径长度是\(46\)，共48.

样例输入2

300

样例输出2

22420

数据范围及限制

共\(10\)组测试数据，每个测试点\( 15\)分。

对于\( 40\%\)的数据，\(1< n\le 15\)。

对于\(100\%\)的数据，\(1< n\le 500\)