题目背景

数学兴趣小组在黑板上从 $1$ 写到 $n$。下课前组长想挑出其中一些数抄进笔记本，但她定了一条规矩：笔记本里任意两个不同的数，差不许是某个正整数的平方。她想抄得尽量多。

题目描述

给定正整数 $n$。请从 $1, 2, \dots, n$ 中选出尽可能多的数组成集合 $S$，使得对 $S$ 中任意两个不同的数 $x, y$，$|x - y|$ 都不是完全平方数（即不存在正整数 $k$ 使 $|x - y| = k^2$）。

请求出 $|S|$ 的最大值。

输入格式

一行一个整数 $n$。

输出格式

一行一个整数，表示最多能选出的数的个数。

输入输出样例 #1

输入 #1

3

输出 #1

2

输入输出样例 #2

输入 #2

6

输出 #2

3

输入输出样例 #3

输入 #3

1

输出 #3

1

说明

样例解释

样例 1：$1$ 与 $2$ 之差为 $1 = 1^2$，$2$ 与 $3$ 之差也是 $1$，都不能同时选；$1$ 与 $3$ 之差为 $2$，可以同时选。故最多选 $2$ 个。

样例 2：$1$ 与 $2$、$2$ 与 $3$、$3$ 与 $4$、$4$ 与 $5$、$5$ 与 $6$ 之差都是 $1$，$1$ 与 $5$、$2$ 与 $6$ 之差都是 $4$。可以选 $1, 3, 6$，两两之差不属于 $\{1, 4\}$；选 $4$ 个数总会撞上这些差，故答案为 $3$。

样例 3：只写了一个数，选上它即可。

数据范围

• 对于 $30\%$ 的数据，$1 \le n \le 8$；
• 对于 $60\%$ 的数据，$1 \le n \le 14$；
• 对于 $100\%$ 的数据，$1 \le n \le 20$。