// Classification of total antisymmetric relations
// See http colon slash slash ruediger-plantiko.blogspot.ch/2016/07/jenseits-von-schere-stein-und-papier.html
// And http colon slash slash ruediger-plantiko.net/relations/ for a JS version

#include <functional>
#include <iostream>
#include <vector>
#include <cstdint>
#include <math.h>
#include <bitset>
#include <algorithm>
#include <unordered_map>

using namespace std;

// ----------------------------------------------------------------------------
// class Bitset
// Homebrewn class for a sequence of bits, can do increments (++ overloaded), 
// bit get, set and unset, and comparisons (== overloaded)
// ----------------------------------------------------------------------------
class Bitset {
  vector<uint32_t> data;
  size_t length;
  size_t maxIndex, maxPlaces;
  uint32_t maxMask;
public:
  Bitset(size_t length, uint32_t word0 = 0 ) : length(length)  {
    this->maxIndex = (size_t) (length/32);
    this->maxPlaces = length % 32 == 0 ? 32 : ( length % 32 );
    this->maxMask = this->maxPlaces < 32 ? ( 1 << this->maxPlaces ) - 1 : 0xffffffff;
    this->data.resize( this->maxIndex + 1, 0 );
    this->data[0] = word0;
    for (size_t i=1;i<=this->maxIndex;i++) this->data[i] = 0;
  }

  Bitset(const Bitset& bs) {
    this->length = bs.length;
    this->maxIndex = bs.maxIndex;
    this->maxPlaces = bs.maxPlaces;
    this->maxMask = bs.maxMask;
    for (size_t i=0;i<=this->maxIndex;i++) this->data.push_back(bs.data[i]);
  }
  
  void toStream(ostream &str) const {
    uint32_t highestWord = this->data[maxIndex];
    for (uint32_t bit = 1<<(this->maxPlaces-1);bit;bit >>=1) {
      str << ((bit & highestWord) ? '1' : '0');
    }
    for (size_t i=this->maxIndex-1;i>=0;i--) str << bitset<32>(this->data[i]); 
  }  
  
  bool equals(const Bitset& bf) const {
    if (this->length != bf.length) return false;
    for (size_t i=0;i<this->maxIndex; i++) 
      if (this->data[i]!=bf.data[i]) return false;
    return (((
      this->data[this->maxIndex]^bf.data[this->maxIndex])
      &this->maxMask)==0);
  }

  bool isZero() {
    for (size_t i=0;i<this->maxIndex;i++) if (this->data[i]!=0) return false;
    return (this->data[this->maxIndex]&this->maxMask)==0;
  }

  bool get(const size_t pos) const {
    return (this->data[(size_t)(pos/32)] & (1 << (pos % 32) )) && true;
  }

  friend bool operator==(const Bitset& lhs, const Bitset& rhs){ 
    return lhs.equals(rhs); 
  }
  friend bool operator!=(const Bitset& lhs, const Bitset& rhs){ 
    return !(lhs == rhs); 
  }
  void clear() {
    for (size_t i=0;i<=this->maxIndex;i++) this->data[i] = 0;
  }
  void set(const size_t pos) {
    this->data[(int)(pos/32)] |= (1 << (pos % 32));
  }
  void unset(const size_t pos) {
    this->data[(int)(pos/32)] &= ~(1 << (pos % 32));
  }
  Bitset& operator++() {
    for (size_t i=0;i<this->maxIndex;i++) {
      if (this->data[i] != 0xffffffff) {
	this->data[i]++;
        return *this;
      }
      else {
	this->data[i] = 0;      
      }    
    }
    if (this->data[this->maxIndex] != this->maxMask) {
      this->data[this->maxIndex]++;
    }
    else {
      this->data[this->maxIndex] = 0;
    }
    return *this;
  }
  Bitset operator++(int) {
    Bitset tmp(*this);
    operator++();
    return tmp;
  }

};

ostream & operator<<(ostream & Str, Bitset const & b) { 
  b.toStream(Str);
  return Str;
}

// ----------------------------------------------------------------------------
// Auxiliary class IndexComputer
// Enumerate all the places of the upper triangle of a N by N matrix
// For each N, there is precisely one instance of IndexComputer
// ----------------------------------------------------------------------------
class IndexComputer {
  typedef struct { int i,j; } pair;
  int N;
  int C,C2;
  double C1,D;
  IndexComputer(int N): N(N) {
    C = 2*N-1;
    C1 = N - 0.499999;
    C2 = C - 2;
    D = C*C/4;
  }
  static vector<IndexComputer*> inst;
public:
  static const IndexComputer* const get(int N) {
    if (inst.size()<N+1){
      for (int i=inst.size();i<N+1;i++)
        inst.push_back( new IndexComputer(i));
    }
    return inst[N];
  } 
  const pair getPair(const int index) const {
    int k = (int)(C1-sqrt(D-2.*index));
    return {k,index+(k-C2)*k/2+1};
  } 
  const int getIndex(const int i,const int j) const {
    return i*N-(i+1)*(i+2)/2+j;
  }
};

vector<IndexComputer*> IndexComputer::inst = {};

// Forward declaration of function permute()
// Needed in DominanceRelation::EquivalenceCheck
void permute(vector<int> numbers,function<bool(const vector<int>&)> f);

// ----------------------------------------------------------------------------
// DominanceRelation is the main class of this program
// An instance represents a total antisymmetric relation
// The key part of the implementation is the check of 
// two instances against each other for equivalence 
// (i.e. is there a permutation of indices transforming the
// first into the second DominanceRelation )
// ----------------------------------------------------------------------------
class DominanceRelation {
	
  const int N, NN;
  const IndexComputer *ic;
  vector<vector<int>> cardinality;
  vector<vector<int>> cycles;
public:
  Bitset* bits;
  DominanceRelation(const int N,Bitset* bits):N(N),NN(N*(N-1)/2),bits(bits) {
    ic = IndexComputer::get(N);
  }
  DominanceRelation(const int N,const function<bool(int,int)> rel):N(N),NN(N*(N-1)/2) {
    ic = IndexComputer::get(N);
    bits = new Bitset(NN);
    for (int i=0;i<NN;i++) {
      auto pair = ic->getPair(i);
      if (rel(pair.i,pair.j)) bits->set(i);
    }
  }
  void bitsChanged() {
    cardinality.resize(0);
    cycles.resize(0);
  }
  const bool isEquivalent( DominanceRelation& r) {
    return EquivalenceCheck(*this,r).areEquivalent();
  }
  const string getCardinalitySignature() {
    const vector<vector<int>>* c = getCardinality();
    vector<int> sizes(N);
    for (int i=0;i<N;i++) sizes[i] = (c->at(i)).size();
    return getSignature( &sizes );
  }
  const vector<vector<int>>* const getCardinality() {
    if (cardinality.size()==0) {
      cardinality.resize(N);
      vector<vector<int>> greaterThan(N);
      for (int i=0;i<NN;i++) {
        auto p = ic->getPair(i);
        if (bits->get(i)) greaterThan[p.i].push_back(p.j);
        else greaterThan[p.j].push_back(p.i); 
      }
      for (int i=0;i<N;i++) {
        cardinality[greaterThan[i].size()].push_back(i);
      }
    } 
    return &cardinality;    
  }
  
  const bool holds(const int i, const int j) const {
    return i == j ? false : 
      i > j ? !bits->get(ic->getIndex(j,i)) : bits->get(ic->getIndex(i,j));
  }
  
  const string getCyclesSignature() {
    const vector<vector<int>>* c = getCycles();
    vector<int> sizes(N+1,0);
    for (int i=0;i<c->size();i++)
      sizes[(c->at(i)).size()]++;
    return getSignature( &sizes );
  }   

  const vector<vector<int>>* getCycles() {
    if (cycles.size()==0) {
      vector<vector<int>> _cycles; 
      for (int i=0;i<N;i++) _getCycles(vector<int>(0),i,&_cycles);
      for (int i=0;i<_cycles.size();i++) {
// Ignore cyclic permutations
        if (min_element(_cycles[i].begin(),_cycles[i].end())==_cycles[i].begin()) {
          cycles.push_back(_cycles[i]); 
        }  
      }
    }
    return &cycles;
  }

  void toStream(ostream & str) const {
    bool doSpace = false;
    str << '{';
    for (int i=0;i<N;i++)
      for (int j=i+1;j<N;j++) 
        if (holds(i,j)) {
          if (doSpace) str << ' ';
          str << i << ':' << j;
          doSpace = true;
        }
    str << '}'; 
  }


private: 
  class EquivalenceCheck {
    int N,NN;
    DominanceRelation & r,& s;
    vector<int> target;
    vector<int>* targetslice;
    vector<vector<int>>& rCard,& sCard;
    vector<vector<int>> possible = { vector<int>(0) };
    vector<vector<int>> new_possible;
    int plen,hlen;
  public:
    EquivalenceCheck(DominanceRelation& s,DominanceRelation& r)
        :r(r),s(s),N(s.N),NN(s.NN),sCard(s.cardinality),rCard(r.cardinality) { }
    bool areEquivalent(vector<int>* perm = 0) {
    	
      if (s.N!=r.N) return false;

      if (sCard.size()==0) s.getCardinality();
      if (rCard.size()==0) r.getCardinality();

      for (int i=0;i<N;i++) 
	    if (sCard[i].size()!=rCard[i].size())
	      return false;
      
      buildTargetFromCardinality();

      function<bool(const vector<int>&)> findNewPossible = [this](const vector<int>& p){
        // Check the new digits against themselves
         if (!this->equalOnSubgroup(p)) return false;
         // Seems to work - combine with formerly proven heads
         this->combineNewWithOld(p);
         return false;
      };

      for (int i=0;i<N;i++) {
        targetslice = & rCard[i];
        plen = targetslice->size( );
        if (plen == 0) continue;
        hlen = possible[0].size(); 
        new_possible.resize(0);
        permute( sCard[i], findNewPossible);
        if (new_possible.size()==0) return false;
        possible = new_possible; 
      }
      
      // We made it! 
      if (perm) { // if the permutation is requested
        perm->resize(N,0);
        vector<int> solution = possible[0];
        for (int i=0;i<N;i++) {
          (*perm)[solution[i]] = target[i];
        }
      }

      return true;
        
    }
  private:
    void buildTargetFromCardinality(  ){
      target.resize(0);
      for (int i=0;i<N;i++) {
	vector<int>* s = &r.cardinality[i]; 
	int n = s->size();
	for (int j=0;j<n;j++) target.push_back((*s)[j]);
      }
    }
    void combineNewWithOld(const vector<int>& p) {
      for (int i=0,posslen=possible.size();i<posslen;i++){
        if (equalsCombination(possible[i],hlen,p,plen)) {
          vector<int> slice(possible[i]);
          slice.insert(slice.end(),p.begin(),p.end());
          new_possible.push_back(slice);
        }
      }
    }
    bool equalOnSubgroup(const vector<int>& p) {
      for (int i=0;i<plen;i++) {
        for (int j=i+1;j<plen;j++) {
          if (!equals(p[i],p[j],targetslice->at(i),targetslice->at(j)))
            return false;
        }
      }
      return true;
    }
    bool equalsCombination(const vector<int>& head, const int hlen,
                           const vector<int>& tail, const int tlen) {
      for (int j=0;j<hlen;j++) {
	for (int k=0;k<tlen;k++) {
	  if (!equals(head[j],tail[k],target[j],targetslice->at(k))) {
	    return false;
	  }
	}
      }
      return true; 
    }
    bool equals(const int i1,const int j1,const int i2,const int j2) {
      return s.holds(i1,j1) == r.holds(i2,j2);
    }
  }; 
  string getSignature(const vector<int>* v) {
    string retval = "(";
    bool doSpace = false;
    int vsize = v->size();
    for (int i=0; i<vsize;i++) {
      int val = v->at(i);
      if (val) {
        if (doSpace) retval += ' ';
        retval += (to_string(i) + ':' + to_string(val));
        doSpace = true;
      }
    }
    retval += ")";
    return retval;
  } 
  void _getCycles(vector<int> a,int next,vector<vector<int>>* _cycles) {
    if (find(a.begin(),a.end(),next)!=a.end()) return;
    int size = a.size();
   
    if (size > 0 && holds(next,a[0])) {
      vector<int> cycle = a;
      cycle.push_back(next);
      _cycles->push_back( cycle );
    }
    if (size >= N) return;
    
    vector<int> slice = a;
    slice.push_back(next);
    for (int i=0;i<N;i++) {
      if (i==next) continue;
      if (holds(next,i)) _getCycles(slice,i,_cycles);    
    }
  }
};

ostream & operator<<(ostream & Str, DominanceRelation const & d) { 
  d.toStream(Str);
  return Str;
}

// ----------------------------------------------------------------------------
// Permute the elements of an array and call a callback for each permutation
// idea from le_m http://stackoverflow.com/questions/9960908/permutations-in-javascript/37580979#37580979
// ----------------------------------------------------------------------------
void permute(vector<int> numbers,function<bool(const vector<int>&)> f) {
    
  int n = numbers.size();
  vector<int> c(n);
  int i = 1, j = 1;

  if (f(numbers)) return;
  while (i < n) {
    if (c[i] < i) {
      int k = (i % 2) ? c[i] : 0,
          p = numbers[i];
      numbers[i] = numbers[k];
      numbers[k] = p;
      c[i]++;
      i = 1;
      if(f(vector<int>(numbers)))return;
    } else {
      c[i] = 0;
      i++;
    }
  }  
}



// ----------------------------------------------------------------------------
// Main program
// Loop over all 2^N*(N-1)/2 dominance relations
// Collect mutually inequivalent dom. rel. in a hash of arrays,
// with the cardinality as key
// ----------------------------------------------------------------------------
int main(int argc, char**argv) {

  typedef struct {
    DominanceRelation* rel;
    int size;
  } t_entry;

  
  string input;
  getline(cin,input);
  int N = atoi(input.c_str()); 
  if (N==0) {
    cerr << "stdin should contain the number N > 0" << endl;
    return 8;
  }

  Bitset bs(N*(N-1)/2);
  DominanceRelation r(N,&bs);
 
  unordered_map<string,vector<t_entry>> classes;
 
  do {
    string cs = r.getCardinalitySignature();
    bool found = false;
    vector<t_entry>& c = classes[cs];
    for (t_entry& f : c) {
      if (f.rel->isEquivalent(r)) {
        found = true;
        f.size+=2;
      } 
    }
    if (!found) {
      auto ne = (t_entry) {
        .rel  = new DominanceRelation(N,new Bitset(*(r.bits))),
        .size = 2,
      };
      c.push_back(ne);
    }
    

// Increment by 2, since the last bit can be determined arbitrarily
// up to equivalence
    bs++;
    if (bs.isZero()) break;
    bs++;
    r.bitsChanged();
  } while( !bs.isZero() );

  int total = 0;
  for (auto pair : classes) {
    cout << pair.first << endl;
    for (auto e : pair.second) {
      cout << "  " << *(e.rel) << endl;
      total ++;
    }
  }
  cout << total << endl;


  return 0;
}