#include <bits/stdc++.h>
using namespace std;
inline long long read() {
  long long a = 0;
  char ch = getchar();
  while (ch < '0' || ch > '9') ch = getchar();
  while (ch >= '0' && ch <= '9')
    a = (a << 3) + (a << 1) + ch - 48, ch = getchar();
  return a;
}
const int N = 1100;
long long n, m, a1[N], b1[N], an[N], bn[N], num[N], g[N];
inline void work(long long x, long long n, long long *d1, long long *dn) {
  if (n == 0)
    d1[0] = dn[0] = 0;
  else if (n == 1)
    d1[1] = (long long)(x == 2), dn[1] = (long long)(x == 1);
  else if (x <= num[n - 1]) {
    work(x, n - 1, d1, dn);
    d1[n] = min(d1[n - 1], dn[n - 1] + 2);
    dn[n] = min(dn[n - 1], d1[n - 1]) + 1 + g[n - 2];
  } else {
    work(x - num[n - 1], n - 2, d1, dn);
    d1[n] = d1[n - 2] + 1;
    dn[n] = dn[n - 2];
  }
}
inline long long DIS(long long u, long long v, long long n) {
  if (n <= 1) return (u != v);
  if (u <= num[n - 1] && v <= num[n - 1])
    return min(DIS(u, v, n - 1),
               min(a1[n - 1] + bn[n - 1], b1[n - 1] + an[n - 1]) + 2);
  else if (u <= num[n - 1] && v > num[n - 1])
    return min(a1[n - 1], an[n - 1]) + b1[n - 2] + 1;
  else
    return DIS(u - num[n - 1], v - num[n - 1], n - 2);
}
int main() {
  m = read();
  n = read();
  n = min(n, (long long)80);
  num[0] = 1, num[1] = 2;
  for (register int i = 2; i <= n; i++) num[i] = num[i - 1] + num[i - 2];
  g[1] = g[2] = 1;
  for (register int i = 3; i <= n; i++) g[i] = g[i - 2] + 1;
  long long u, v;
  while (m--) {
    u = read(), v = read();
    if (u > v) swap(u, v);
    work(u, n, a1, an);
    work(v, n, b1, bn);
    printf("%d\n", DIS(u, v, n));
  }
  return 0;
}
