#include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <fstream>

 #include <ctime>

 #include <cmath>

 #include <cstdlib>

 #include <algorithm>

 #include <set>

 #include <map>

 #include <list>

 #include <stack>

 #include <queue>

 #include <iterator>

 #include <vector>

 using namespace std;

 #define LL long long

 #define INF 0x3f3f3f3f

 #define MOD 1000000007

 #define MAXN 10000010

 #define MAXM 1000010

 const int maxn = ;

 int a[maxn];

 void euler_phi(int n)

 {

     int m = (int)sqrt(n+0.5);

     //int ans = n;

     for(int i = ; i <= m; i++ )

         if(n%i==)

         {

             //ans = ans/i*(i-1);

             while(n%i==)

             {

                 a[i]++;

                 n /= i;

             }

         }

     if(n > )

         a[n]++;

 //        ans = ans/n*(n-1);

 //    return ans;

 }

 int main()

 {

     int n;

     int kase = ;

     while(scanf("%d", &n)==&&n>=)

     {

         if(kase)

             printf("\n");

         memset(a, , sizeof(a));

         euler_phi(n);

         printf("Case %d.\n", ++kase);

         for(int i = ; i <= n; i++ )

             if(a[i])

                 printf("%d %d ", i, a[i]);

         printf("\n");

     }

     return ;

 }