Description

对于任何正整数x，其约数的个数记做g(x)。例如g(1)=1，g(6)=4。

如果某个正整数x满足：对于任意i(0 < i < x)，都有g(i) < g(x)，则称x为反素数。

Input

输入数据有多行，每行包括一个整数n(1 <= n < 665281)。

Output

对于输入的每个n,输出[1..n]范围内的最大的反素数。

Sample

Input

1000

Output

840

Source: lcs