EKG序列是一个由正整数构成的序列。此序列的前两个数是1和2。此后每一个数都选自与前 一个数有公因子且没有在序列中出现过的数中的最小数。因此,EKG序列的第三个数是4,然后是6,接着是3。此序列的 前面几个数如下:
    1, 2, 4, 6, 3, 9, 12, 8, 10, 5, 15, 18, 14, 7, 21, 24, 16, 20, 22, 11, 33, 27
    这个序列有两个有趣的特性:1、所有的正整数都会在序列中出现;2、所有的素数在此序列中 以升序排列。你的工作是找到某一个正整数在EKG序列中的位置。

输入

    输入有多行,每行为一组测试数据。每组测试数据为一个正整数n(n位于[1, 300000]中)。
    如果输入为0,则表示输入结束,这一行不需要处理。
    注意:EKG序列中前300000个整数中不含有大于1000000的整数。

输出

    对于每组测试数据,输出一行,这一行中有一个数,表示n在EKG序列中的位置p。
    可以保证,所有的p不会大于1000000。

输入示例

12
21
2
33
100000
299977
0

输出示例

7
15
2
21
97110
584871

2003 East Central Regional Contest