#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

template<class T>
string str( const vector<T>& v )
{
   stringstream ss;
   for ( int i = 0; i < (int)v.size(); i++ )
      ss << (i?",":"") << v[i];
   return "{" + ss.str() + "}";
}

void getPrimeFactorsSig( __int64 x, vector<int>& v )
{
   v.clear();
   for ( __int64 i = 2; i*i <= x; i++ )
   {
      int power = 0;
      while ( x % i == 0 )
         x /= i, ++power;
      if ( power )
         v.push_back( power );
   }
   if ( x != 1 )
      v.push_back( 1 );
   sort( v.begin(), v.end() );
}
vector<int> getPrimeFactorsSig( __int64 x )
{
   vector<int> v;
   getPrimeFactorsSig( x, v );
   return v;
}

void main()
{
   __int64 K = 1000000000LL;
   for ( __int64 i = K + 0; i < K + 4000; i++ )
   {
      vector<int> a = getPrimeFactorsSig( i );
      vector<int> b = getPrimeFactorsSig( i+1 );
      if ( a == b )
      {
         cout << i << " " << str(a) << endl;
      }
   }
}