#include <iostream>
    using namespace std;
     
    int main() {
      // your code goes here
      auto l =
      [](int n){int k=1,x,a,b,t,d=1;for(;d;)for(d=x=0;++x<n;d=a<2&t>1?k++:d){for(a=x,b=n;t=b;a=t)b=a%b;for(t=1,b=k;b--;t=t*x%n);}return k;};
      for( int i = 1; i < 100; i++ ) {
      	std::cout<<i<<' '<<l(i)<<'\n';
      }
    }