#include <bits/stdc++.h>
using namespace std;
template <typename tp>
void read(tp& x) {
  x = 0;
  char c = getchar();
  bool sgn = 0;
  while ((c < '0' || c > '9') && c != '-') c = getchar();
  if (c == '-') sgn = 1, c = getchar();
  while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
  if (sgn) x = -x;
}
template <typename tp>
void write(tp x) {
  if (x < 0)
    putchar('-'), write(-x);
  else {
    if (x >= 10) write(x / 10);
    putchar(x % 10 + '0');
  }
}
long long n, sz[1003], disst[1003], dissx[1003], distx[1003], dissy[1003],
    disty[1003];
void w(long long x, long long n, long long diss[], long long dist[]) {
  if (n == 0) {
    diss[0] = dist[0] = 0;
    return;
  }
  if (n == 1) {
    if (x == 1)
      diss[1] = 0, dist[1] = 1;
    else
      diss[1] = 1, dist[1] = 0;
    return;
  }
  if (x <= sz[n - 1]) {
    w(x, n - 1, diss, dist);
    diss[n] = min(diss[n - 1], dist[n - 1] + 2);
    dist[n] =
        min(diss[n - 1] + 1 + disst[n - 2], dist[n - 1] + 1 + disst[n - 2]);
  } else {
    w(x - sz[n - 1], n - 2, diss, dist);
    diss[n] = diss[n - 2] + 1;
    dist[n] = dist[n - 2];
  }
}
long long solve(long long x, long long y, long long n) {
  if (n == 1) return x != y;
  if (x <= sz[n - 1] && y <= sz[n - 1]) {
    return min(
        min(dissx[n - 1] + disty[n - 1] + 2, distx[n - 1] + dissy[n - 1] + 2),
        solve(x, y, n - 1));
  } else if (x <= sz[n - 1] && y > sz[n - 1]) {
    return min(dissx[n - 1] + 1 + dissy[n - 2],
               distx[n - 1] + 1 + dissy[n - 2]);
  } else if (x > sz[n - 1] && y > sz[n - 1]) {
    return solve(x - sz[n - 1], y - sz[n - 1], n - 2);
  }
}
int main() {
  long long T;
  read(T), read(n);
  if (n > 77) n = 77;
  sz[0] = 1, sz[1] = 2;
  disst[0] = 0, disst[1] = 1;
  for (long long i = 2; i <= n; i++)
    sz[i] = sz[i - 1] + sz[i - 2], disst[i] = disst[i - 2] + 1;
  while (T--) {
    long long x, y;
    read(x), read(y);
    if (x > y) swap(x, y);
    w(x, n, dissx, distx);
    w(y, n, dissy, disty);
    write(solve(x, y, n)), putchar('\n');
  }
  return 0;
}
