#include <bits/stdc++.h>
using namespace std;
long long rd() {
  long long x = 0, y = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') y = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    x = (x << 1) + (x << 3) + c - '0';
    c = getchar();
  }
  return x * y;
}
long long T, n, sm[105], d[105], d1[105], d2[105], d3[105], d4[105];
void pre(long long x, long long nw, long long t1[], long long t2[]) {
  if (nw == 0) return;
  if (nw == 1) {
    t1[1] = (x == 2);
    t2[1] = (x == 1);
    return;
  }
  if (x <= sm[nw - 1]) {
    pre(x, nw - 1, t1, t2);
    t1[nw] = min(t1[nw - 1], t2[nw - 1] + 2);
    t2[nw] = min(t1[nw - 1], t2[nw - 1]) + d[nw - 2] + 1;
  } else {
    pre(x - sm[nw - 1], nw - 2, t1, t2);
    t1[nw] = t1[nw - 2] + 1;
    t2[nw] = t2[nw - 2];
  }
}
long long qy(long long x, long long y, long long nw) {
  if (nw <= 1) return x != y;
  if (x < sm[nw - 1] + 1 && y >= sm[nw - 1] + 1)
    return min(d1[nw - 1], d2[nw - 1]) + d3[nw - 2] + 1;
  if (x < sm[nw - 1] + 1 && y < sm[nw - 1] + 1)
    return min(qy(x, y, nw - 1),
               min(d1[nw - 1] + d4[nw - 1], d2[nw - 1] + d3[nw - 1]) + 2);
  return qy(x - sm[nw - 1], y - sm[nw - 1], nw - 2);
}
int main() {
  T = rd();
  n = rd();
  n = min(n, (long long)80);
  sm[0] = 1;
  sm[1] = 2;
  d[0] = 0;
  d[1] = 1;
  for (register int i = 2; i <= n; i++)
    sm[i] = sm[i - 1] + sm[i - 2], d[i] = d[i - 2] + 1;
  n = min(n, (long long)80);
  while (T--) {
    long long x = rd(), y = rd();
    if (x > y) swap(x, y);
    pre(x, n, d1, d2);
    pre(y, n, d3, d4);
    printf("%lld\n", qy(x, y, n));
  }
  return 0;
}
