EKG Sequence

The EKG sequence is a sequence of positive integers built as follows. The first two terms are 1 and 2. Each later term is the smallest positive integer that has not been used yet and that shares a common factor greater than 1 with the immediately preceding term (that is, it is not coprime with it). So the third term is 4 (the smallest even number not yet used); the next is 6, and the next is 3. The first few terms of the sequence are:

1, 2, 4, 6, 3, 9, 12, 8, 10, 5, 15, 18, 14, 7, 21, 24, 16, 20, 22, 11, 33, 27

The sequence is named after an EKG (electrocardiogram) because of its erratic up-and-down fluctuations. It has a few interesting but non-trivial properties: every positive integer eventually appears in the sequence, and all primes appear in increasing order. Your task is to find the position of a given integer in the sequence.

The input consists of several test cases. Each case is a line containing a single integer $n$ ($1 \le n \le 300000$). A line containing 0 follows the last test case. The prefix of the EKG sequence that contains every integer up to 300,000 does not contain any integer greater than 1,000,000.

For each test case, print one line in the following format:

The number n appears in location p.

where $n$ is the given number and $p$ is the position at which it appears in the EKG sequence. It is guaranteed that $p$ will be no larger than 1,000,000.