Description

明天就是区域赛选拔了，出题人还是大师兄。
有道题目只需要输出一行一个整数，而且这个整数在\(1\)到\(n\)之间（包含\(1\)和\(n\)）。
你知道大师兄每次只喜欢出一组数据，所以你决定贿赂大师兄来得到这组数据的答案。
你每次可以给大师兄一万元，然后告诉他一个同样在\(1\)到\(n\)之间（包含\(1\)和\(n\)）的数字，如果刚好猜对了，他就会说：“那真的牛批”，否则他会告诉你这个数字和答案的最大公约数。
求最坏情况下，你至少要花多少万，才能确保猜中答案，请注意，不一定需要大师兄说出“那真的牛批”，只需要你自己心里能知道答案就好。

Format

Input

每个测试点包含不超过\(10\)组测试数据，请处理至文件结束。
每组数据包含一行一个整数\(n(1<=n<=10^9)\)。

Output

按照输入顺序，对于每组数据输出一行一个整数，表示对应的最少花费。

Sample 1

Input

6
6324

Output

2
802

Limitation

1s, 1GB for each test case.

Source

Vijos Original