You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

如果拯救你是一种罪，那就让我来当这个罪人…

这个世界的确不美好，但是不要放弃，永远都不要放弃，去把这个不完美的故事变成我们所期望的样子…

世界当然不够美好，但也有人叫我不要放弃。她们指引着我，向我证明这个世界没有那么糟糕。我爱她们，也爱她们所爱的一切。这把剑连接着我们，她会烧尽漆黑的天空，让光照向更远的地方，这就是我和大家回家的路！

为世界上所有的美好而战！！

Description

现在琪亚娜得到了一个1~n的n个数字，她想将这n个数字首尾连接组成一个环，使得相邻元素互质的对数尽可能多。请输出最大对数。

Format

Input

第一行输入一个n表示有n个互不相同的数字$(2<n<=10000000000)$

Output

最多的互质的对数

Samples

4

4

hint

1 4 3 2

Limitation

1s, 1024KiB for each test case.