路径

时间限制: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$