#include <bits/stdc++.h>
const int MAXN = 80 + 5;
long long f[MAXN];
inline char nc() {
  static char buf[1000000 + 3], *p1 = buf + 1000000 + 3,
                                *p2 = buf + 1000000 + 3;
  if (p1 == p2) {
    p1 = buf;
    p2 = buf + fread(buf, 1, 1000000 + 3, stdin);
    if (p1 == p2) return -1;
  }
  return *p1++;
}
template <typename T>
inline void read(T &x) {
  x = 0;
  int flag = 0;
  char ch = nc();
  while (!isdigit(ch)) {
    if (ch == '-') flag = 1;
    ch = nc();
  }
  while (isdigit(ch)) {
    x = (x << 1) + (x << 3) + (ch ^ '0');
    ch = nc();
  }
  if (flag) x = -x;
}
long long d[2][2][MAXN];
inline long long work(long long u, long long v, int n) {
  if (u == v) return 0;
  if (u + 1 == v) return 1;
  long long ls = f[n - 1];
  long long res = 0;
  if (u > ls && v > ls)
    res = work(u - ls, v - ls, n - 2);
  else if (u <= ls && v <= ls)
    res = std::min({work(u, v, n - 1), d[0][0][n - 1] + d[1][1][n - 1] + 2,
                    d[0][1][n - 1] + d[1][0][n - 1] + 2});
  else
    res = std::min(d[0][0][n - 1], d[0][1][n - 1]) + d[1][0][n - 2] + 1;
  return res;
}
long long t[MAXN];
inline void prework(long long v, int n, long long t1[], long long tn[]) {
  if (n == 0) {
    t1[n] = tn[n] = 0;
    return;
  }
  if (n == 1) {
    t1[n] = (v != 1);
    tn[n] = (v != 2);
    return;
  }
  long long ls = f[n - 1];
  if (v <= ls) {
    prework(v, n - 1, t1, tn);
    t1[n] = std::min(t1[n - 1], tn[n - 1] + 2);
    tn[n] = std::min(tn[n - 1], t1[n - 1]) + 1 + t[n - 2];
  } else {
    prework(v - ls, n - 2, t1, tn);
    t1[n] = t1[n - 2] + 1;
    tn[n] = tn[n - 2];
  }
}
int main() {
  f[0] = 1;
  f[1] = 2;
  t[0] = 0;
  t[1] = 1;
  for (int i = 2; i <= 90; ++i) f[i] = f[i - 1] + f[i - 2], t[i] = t[i - 2] + 1;
  int q, n;
  read(q);
  read(n);
  n = std::min(n, 80);
  for (int i = 1; i <= q; ++i) {
    long long u, v;
    read(u);
    read(v);
    if (u > v) std::swap(u, v);
    prework(u, n, d[0][0], d[0][1]);
    prework(v, n, d[1][0], d[1][1]);
    printf("%lld\n", work(u, v, n));
  }
  return 0;
}
