// Solution to EKG by Bob Roos (version 3)
// My first two versions just bogged down, so I finally threw in the
// towel and looked at the algorithm given in:
// 
//    J. C. Lagarias, E. M. Rains, N. J. A. Sloane.
//    The EKG Sequence.
//    http://xxx.lanl.gov/abs/math.NT/0204011
//
// Even then it was pretty rough going; I had to change at least one
// thing in their algorithm (they start with an initial "guess" for
// the next element of the sequence equal to the goal value, but
// sometimes this "initial guess" caused problems, so I changed it).

import java.util.*;
import java.io.*;

public class EKG {
 // For details of most of these, see the Lagarias, Rains, and Sloane paper
  public static boolean hit[] = new boolean[1000001];
  public static int a[] = new int[1000001];
  public static int small[] = new int[1000001];
  public static int quot[] = new int[1000001];
  public static int gap[] = new int[1000001];

 // Remember where the last "smallest prime power" occurred when index = prime
  public static int lastsmall[] = new int[1000001];

 // Number of elements generated so far:
  public static int count = 2;

  public static void main(String[] args) throws IOException {
    BufferedReader in =
      new BufferedReader(new InputStreamReader(System.in));

    int n;
    setup();
    while ((n = Integer.parseInt(in.readLine().trim())) != 0) {
      System.out.println("The number " + n + " appears in location " +
         (ekg(n))+".");
    }
  }

  public static int ekg(int n) {
   // First, search already-generated values:
    for (int i = 1; i <= count; i++)
      if (n == a[i])
        return i;

   // Not there, so extend the search using Lagarias, Rains, Sloane
   // algorithm:

    int an = a[count];         // last know value in sequence
    while (a[count] != n) {    // search until we find n...
      int k = a[count];
      int B = 3*k;
      while (k > 1) {          // find smallest unused multiple of any
        int p = small[k];      // prime divisor of a[count]...
        B = Math.min(B,gap[p]);
        k = quot[k];
      }
      an = B;                  //...which is our new element
      count++;
      hit[B] = true;
      a[count] = an;

     // Finally, for each prime divisor of the new value, update the
     // value of the "largest multiple used so far":
      int p = small[an];
      while (p > 1) {
        int j = lastsmall[p];
        while (j < 1000001 && hit[j])
          j += p;
        gap[p] = j;
        lastsmall[p] = j;
        an = quot[an];
        p = small[an];
      }
    }

    return count;
  }



 // Initialize tables:
  public static void setup() {
   // "Hit" array initially contains only the values 1 and 2:
    hit [1] = hit[2] = true;
    for (int i = 3; i < 1000001; i++) {
      hit[i] = false;
    }

   // Initially only the first two sequence elements are known:
    a[1] = 1; a[2] = 2;

   // Find smallest prime divisor and largest factor not containing
   // smallest prime factor for each positive integer; also remember
   // the last known location of the "smallest unused multiple" of 
   // each prime is located:

    small[1] = 1; small[2]=2;
    quot[1] = quot[2] = 1;
    lastsmall[2] = 2;

    for (int i = 3; i < 1000001; i++) {
     // Find smallest prime divisor of i:
      int limit = (int)(Math.sqrt(i)+.5);
      if (i%2 == 0) {
        small[i] = 2;
      }
      else if (i%3 == 0) {
        small[i] = 3;
      }
      else {
        small[i] = i;
        for (int div = 3; div <= limit; div += 2) {
          if (i%div == 0) {
            small[i] = div;
            break;
          }
        }
      }
      lastsmall[i] = i;

     // Find largest factor not containing small[i]:
      int quo = i/small[i];
      gap[i] = i;
      while (quo > 1 && quo%small[i] == 0) {
        quo = quo/small[i];
      }
      quot[i] = quo;
    }

   // Lowest unused multiples:
    gap[1] = 1; gap[2] = 4;
  }
}