#include <bits/stdc++.h>
using namespace std;
int n, m, a0[80], a1[80], b0[80], b1[80];
long long f[100], u, v;
void prepare(long long x, int n, int *a0, int *a1) {
  if (n == 0) {
    a0[n] = a1[n] = 0;
    return;
  }
  if (n == 1) {
    prepare(x, n - 1, a0, a1);
    a0[n] = (x == 2), a1[n] = (x == 1);
    return;
  }
  if (x <= f[n - 1]) {
    prepare(x, n - 1, a0, a1);
    a0[n] = min(a0[n - 1], a1[n - 1] + 2);
    a1[n] = min(a0[n - 1], a1[n - 1]) + 1 + (n - 1) / 2;
  } else {
    prepare(x - f[n - 1], n - 2, a0, a1);
    a0[n] = a0[n - 2] + 1;
    a1[n] = a1[n - 2];
  }
}
int dist(long long x, long long y, int n) {
  if (n <= 1) return x != y;
  if ((x <= f[n - 1]) && (f[n - 1] < y))
    return min(a0[n - 1], a1[n - 1]) + b0[n - 2] + 1;
  if ((x <= f[n - 1]) && (y <= f[n - 1]))
    return min(dist(x, y, n - 1),
               min(a0[n - 1] + b1[n - 1], b0[n - 1] + a1[n - 1]) + 2);
  return dist(x - f[n - 1], y - f[n - 1], n - 2);
}
void work() {
  scanf("%d %d", &m, &n), n = min(n, 79);
  f[0] = 1, f[1] = 2;
  for (int i = 2; i <= n; i++) f[i] = f[i - 1] + f[i - 2];
  for (int i = 1; i <= m; i++) {
    scanf("%lld %lld", &u, &v);
    if (u > v) swap(u, v);
    prepare(u, n, a0, a1), prepare(v, n, b0, b1);
    printf("%d\n", dist(u, v, n));
  }
}
int main() {
  work();
  return 0;
}
