/* Problem 3--Making Stars
   If you know a little number theory, the number of stars is equal to
   phi(n)/2-1, where phi(n) is the number of positive integers less than
   n relatively prime to n. */

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main (int argc, char **argv);
int phi (int n);

int main (int argc, char **argv) {

  int n, cs;
  FILE *in, *out;

 in = fopen ("prob3.in","r");
 out = fopen ("prob3.out","w");
 for (cs=1;fscanf (in,"%d",&n),n>0;cs++)
  fprintf (out,"Case %d, n = %d, unique stars = %d\n",cs,n,phi(n)/2-1);
 fclose (in);
 fclose (out);
 return EXIT_SUCCESS;
}

/* Computes and returns phi(n) as described above.  The standard formula
   involves factoring n into prime powers. */

int phi (int n) {

  int prod, p, t;

 for (prod=1,p=2;p*p<=n;p++) {
  t = 0;
  for (t=0;n%p==0;t++)  /* How many prime factors of p goes into n? */
   n /= p;
  if (t > 0)  /* Add this prime power to the phi formula */
   prod *= (p-1) * (int) (0.5 + pow (p,t-1));
 }
 if (n > 1) /* The number left over is prime */
  prod *= n-1;
 return prod;
}