#include <iostream>
#include <set>
#include <deque>

using namespace std;

typedef unsigned long long uint64;
typedef  pair<uint64, short> node;

set< uint64 > done;
deque<node> dq;

short zero(uint64 v) {
  short answer = 0;
  while (v & 15) {
    answer++;
    v >>= 4;
  }
  return answer;
}

void dview(uint64 v) {
  if (v) {
    dview(v >> 4);
    cout << (v & 15) << " ";
  }
}

uint64 mask[16];
uint64 nmask[16];


int main() {
  int ar[16] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0};
  uint64 v = 0ll;
  for (int i=0;i<16;i++) {
    v <<= 4; v += ar[i];
    mask[i] = 15ll << (i*4);
    nmask[i] = ~mask[i];
//    dview(mask[i]); cout << "\n";
//    dview(nmask[i]); cout << "\n";
  }
  //cout << v << "\n";
  dq.push_back(node(v,0));
  short z=0;int pos=0;
int lastsie=-1;
  while (dq.front().second<50) {
if (dq.front().second > lastsie) {
cout << lastsie << " " << pos << "\n";
  lastsie = dq.front().second;
  pos=0;
}
pos++;
    v = dq.front().first;
    if (done.find(v) == done.end()) {
      z = zero(v);
      done.insert(v);
//      cout << dq.front().second << " " << v << "\n";
      //dview(v); cout << "\n";
      //cout << "z is " << z << "\n";
      if (z % 4 != 3) {
        // move west
        //cout << "west\n";
        dq.push_back(node(
         ((v&nmask[z+1])|((v&mask[z+1])>> 4))
        ,dq.front().second+1));
      }
      if (z % 4 != 0) {
        // move east
        //cout << "east\n";
        dq.push_back(node(
         (v&nmask[z-1])|((v&mask[z-1]) << 4)
        ,dq.front().second+1));
      }
      if (z < 12) {
        // move north
        //cout << "nortH\n";
        dq.push_back(node(
         (v&nmask[z+4])|((v&mask[z+4]) >> 16)
        ,dq.front().second+1));
      }
      if (z >= 4) {
        // move south
        //cout << "soutH\n";
        dq.push_back(node(
         (v&nmask[z-4])|((v&mask[z-4]) << 16)
        ,dq.front().second+1));
      }
    }
    dq.pop_front();
  }
  while (!(dq.empty())) {
    v = dq.front().first;
    if (done.find(v) == done.end()) {
 //     cout << dq.front().second << " " << v << "\n";
      //dview(dq.front().first); cout << "\n";
      done.insert(v);
    }
    dq.pop_front();
  }
}