#include <bits/stdc++.h>
using namespace std;
long long n, m, a1[1000], a2[1000], b1[1000], b2[1000];
long long f[1000];
void pre(long long x, long long n, long long *a1, long long *a2) {
  if (n == 0) {
    a1[n] = a2[n] = 0;
    return;
  }
  if (n == 1) {
    pre(x, n - 1, a1, a2);
    a1[n] = (x == 2);
    a2[n] = (x == 1);
    return;
  }
  if (x <= f[n - 1]) {
    pre(x, n - 1, a1, a2);
    a1[n] = min(a1[n - 1], a2[n - 1] + 2);
    a2[n] = min(a1[n - 1], a2[n - 1]) + (n - 1) / 2 + 1;
  } else {
    pre(x - f[n - 1], n - 2, a1, a2);
    a1[n] = a1[n - 2] + 1;
    a2[n] = a2[n - 2];
  }
}
long long dis(long long x, long long y, long long n) {
  if (n <= 1) return x != y;
  if (x <= f[n - 1] && f[n - 1] < y)
    return min(a1[n - 1], a2[n - 1]) + b1[n - 2] + 1;
  if (x <= f[n - 1] && y <= f[n - 1]) {
    return min(dis(x, y, n - 1),
               min(a1[n - 1] + b2[n - 1], b1[n - 1] + a2[n - 1]) + 2);
  }
  return dis(x - f[n - 1], y - f[n - 1], n - 2);
}
int main() {
  cin >> m >> n;
  if (n > 79) 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) {
    long long u, v;
    cin >> u >> v;
    if (u > v) swap(u, v);
    pre(u, n, a1, a2);
    pre(v, n, b1, b2);
    cout << dis(u, v, n) << endl;
  }
  return 0;
}
