报纸
题目背景
终于熬过了初中三年,《学英语报》却阴魂不散。当高一的第一张《学英语报》飘到我面前时,CYD 大神心里充满了绝望,然而,他还有一线希望——XHY 同学总是做得比他快。
题目描述
作为做 PPT 的回报,XHY 同学决定送点“温暖”给 CYD 大神——一份英语报纸的答案。这份报纸是一个 $N \times N$ 的方阵,其中某些格子写有答案。答案的分布似乎很有规律:对于格子 $(x,y)$,当且仅当 $x$ 和 $y$ 不互质时,这个格子上有答案。
XHY 同学的手机每次能拍下一个 $1 \times 2$ 的区域(横竖均可)。请你帮她写一个程序,求出至少要拍多少张照片,才能把所有的答案发给 CYD 大神。
输入输出格式
输入格式
仅一行,一个正整数 $N$。
输出格式
仅一行,一个非负整数表示至少要拍的照片张数。
输入输出样例
输入样例 #1
4
输出样例 #1
5
输入样例 #2
5
输出样例 #2
6
输入样例 #3
6
输出样例 #3
11
说明
对于 $30 \%$ 数据,$N \le 10$。
对于 $60 \%$ 数据,$N \le 50$。
对于 $100 \%$ 数据,$1 \le N \le 233$。