负责人

• CFCOI_official
• zhangruixiang
• Hamburger999
• 035966_L3

注意

本题需要使用文件读写（tsp.in / tsp.out）。

作为提示，$\bm{1,2,\ldots,10^8}$ 中共有 $\bm{5761455}$ 个质数。

对于很大的 bool 类型数组（每个元素占用 $\bm 1$ 字节），可以考虑使用 std::bitset（使用时需要包含 <bitset> 或 <bits/stdc++.h> 头文件）进行存储（每 $\bm 8$ 个元素占用 $\bm 1$ 字节）以节省空间。例如，可以使用 std::bitset <12345678> b 来定义一个大小为 $\bm{12345678}$，名称为 $\bm b$ 的 bool 类型数组。

可以证明，在本题的数据范围下，答案不超过 $\bm{10^9}$。也就是说，你可以直接使用 $\bm{32}$ 位有符号整数（或 $\bm{32}$ 位无符号整数）进行运算。

题目背景

Sleeping Hippo 是一个旅行商，现在他坐在 Bizy 国首都的火车站中。

Bizy 国有若干个城市，其中第一个城市是首都。

对于任意两个 Bizy 国的城市：

• 若两个城市的编号中至少有一个数是质数，则它们存在一条双向的火车线路，票价为二者编号之差。
• 否则，不存在往返于这两个城市的火车线路。

此外，为了促进贸易，对于任意一条火车线路：

• 如果 Sleeping Hippo 没有搭乘过这个线路，则不需要买票。
• 如果 Sleeping Hippo 搭乘过恰好一次这个线路，则需要买一张票，支付二者编号之差的票价。
• 如果 Sleeping Hippo 搭乘过超过一次这个线路，则只需要买一张票，支付二者编号之差的票价。

现在 Sleeping Hippo 需要访问每个城市至少一次（此处认为 Sleeping Hippo 出发前就访问了首都），求他需要支付的票价之和的最小值。

题目描述

给定一张 $n$ 个结点（编号从 $1$ 开始）的无向图，两个结点 $u, v\ (1 \le u < v \le n)$ 之间有连边当且仅当 $u, v$ 中至少有一个是质数，且该边的边权为 $v - u$。

试求出该图的最小生成树的边权之和。（可以证明这张图是连通的。）

输入格式

一行一个正整数 $n\ (1 \le n \le 10^8)$。

输出格式

一行一个非负整数表示答案。

样例

1

0

2

1

3

2

4

3

5

4

6

5

7

6

8

7

样例解释

在所有的样例中，选取 $1 \leftrightarrow 2 \leftrightarrow \ldots \leftrightarrow n$ 的一条链作为生成树都是最优的，此时的答案为 $n - 1$。