1850年，英格兰教会的一个教区长柯克曼（T. P. Kirkman）提出了一个有趣的女生散步问题。在某女子学校中，$15$ 个女学生同在一个学组。她们每天都要去校外散步。为了加强她们的相互了解，增进友谊，柯克曼设想，如果将女生适当分成 $5$ 组，每组有 $3$ 位女生，使每个女生在 $7$ 天之内，都能够与别的女学生有且仅有一次同组机会。如何分组才能达到此目的？
这个似乎很简单的问题，却有不同寻常的分组算法。这就是后来称为柯克曼三元系的分组算法。过了一百多年，又发明了许多有趣的女生散步分组算法。其中的一个有趣的随机圆环分组算法描述如下。
设有 $n$ 个待分组的女生。首先随机分配给每位女生一个不同的编号。这 $n$ 个女生的编号组成的集合恰为 $[1, n]$。分在同一组的女生可以自由地在草地上围坐成一个圆圈。圆圈中的每位女生需要满足如下条件，即她的编号和她左右邻座女生编号的乘积均小于 $n$。当圆圈中只有一个女生时，其自身的编号小于 $n$。满足上述条件的女生分为一组。其余女生继续按此方法分组。
女生散步问题：对于给定的一个整数 $n$，计算最多有多少位女生可分在同一组。
输入格式
依次给出待计算的多个测试数据。每行给出由一个整数 $n$ ，表示有 $n$ 个待分组的女生。
输出格式
对于输入文件中的每个测试数据 $n$，输出这个待分组的女生中，最多有多少位女生可分在同一组，每行输出一个计算结果。
样例数据
样例输入
2
3
5
7
8样例输出
1
2
2
3
3子任务
| 测试点编号 | $n$ |
|---|---|
| $1 \sim 5$ | $n \leq 600\,000$ |
| $6 \sim 8$ | $n \leq 50\,000\,005$ |
| $9 \sim 10$ | $n \leq 1\,000\,000\,000$ |
注
- 赛时并未提供数据组数，“请选手自行评估”。
- 题目中的描述存在歧义，但赛时并未给出任何解释。