描述

EKG 序列是一个由正整数组成的序列，其生成方式如下：该序列的前两个数是$1$和$2$。后续的每一项都是尚未使用过的、且与前一项有公因数的最小正整数。所以，该序列的第三项是$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

这个序列因其相当不规则的波动而得名。该序列有一些有趣但并非显而易见的性质。其中一个性质是所有正整数最终都会出现在这个序列中。另一个性质是所有的质数会按递增顺序出现在序列中。你的任务是找出给定整数在该序列中的位置。

输入

输入由多个测试用例组成。每个测试用例将是包含一个整数$n$的一行，其中$1 \leq n \leq 300000$。在最后一个测试用例之后输入一个$0$。请注意，包含所有小于等于$300000$的整数的 EKG 序列部分不会包含大于$1000000$的整数。

输出

每个测试用例应产生一行如下形式的输出：

The number $n$ appears in location $p$.

其中$n$是给定的数字，$p$是$n$在 EKG 序列中的位置。可以保证$p$不会大于$1000000$。

输入数据 1

12
21
2
33
100000
299977
0

输出数据 1

The number 12 appears in location 7.
The number 21 appears in location 15.
The number 2 appears in location 2.
The number 33 appears in location 21.
The number 100000 appears in location 97110.
The number 299977 appears in location 584871.

来源

2003年美国中东部地区竞赛