#include <bits/stdc++.h>
using namespace std;
long long f[80];
int x[80][2], y[80][2];
pair<int, int> getx(long long p, int n) {
  pair<int, int> t;
  if (n == 0) return pair<int, int>(0, 0);
  if (n == 1) return pair<int, int>(p != 1, p != 2);
  if (p == 1) return pair<int, int>(0, (n + 1) / 2);
  if (p == f[n]) return pair<int, int>((n + 1) / 2, 0);
  if (x[n][0] != -1) return pair<int, int>(x[n][0], x[n][1]);
  if (p > f[n - 1]) {
    t = getx(p - f[n - 1], n - 2);
    x[n][0] = t.first + 1;
    x[n][1] = t.second;
  } else {
    t = getx(p, n - 1);
    x[n][0] = min(t.first, t.second + 2);
    x[n][1] = min(t.first, t.second) + (n + 1) / 2;
  }
  return pair<int, int>(x[n][0], x[n][1]);
}
pair<int, int> gety(long long p, int n) {
  pair<int, int> t;
  if (n == 0) return pair<int, int>(0, 0);
  if (n == 1) return pair<int, int>(p != 1, p != 2);
  if (p == 1) return pair<int, int>(0, (n + 1) / 2);
  if (p == f[n]) return pair<int, int>((n + 1) / 2, 0);
  if (y[n][0] != -1) return pair<int, int>(y[n][0], y[n][1]);
  if (p > f[n - 1]) {
    t = gety(p - f[n - 1], n - 2);
    y[n][0] = t.first + 1;
    y[n][1] = t.second;
  } else {
    t = gety(p, n - 1);
    y[n][0] = min(t.first, t.second + 2);
    y[n][1] = min(t.first, t.second) + (n + 1) / 2;
  }
  return pair<int, int>(y[n][0], y[n][1]);
}
int go(long long l, long long r, int n) {
  pair<int, int> t, tt;
  if (r - l <= 1) return r - l;
  if (l == 1 && r == f[n]) return (n + 1) / 2;
  if (l > f[n - 1]) return go(l - f[n - 1], r - f[n - 1], n - 2);
  if (r > f[n - 1]) {
    t = getx(l, n - 1);
    return gety(r - f[n - 1], n - 2).first + min(t.first, t.second) + 1;
  }
  t = getx(l, n - 1);
  tt = gety(r, n - 1);
  return min(go(l, r, n - 1),
             min(t.first, t.second) + min(tt.first, tt.second) + 2);
}
int main() {
  int n, m;
  cin >> m >> n;
  f[0] = 1, f[1] = 2;
  for (int i = 2; i < 80; i++) f[i] = f[i - 1] + f[i - 2];
  while (m--) {
    memset(x, -1, sizeof(x));
    memset(y, -1, sizeof(y));
    long long s, e;
    cin >> s >> e;
    if (s > e) swap(s, e);
    printf("%d\n", go(s, e, min(n, 80 - 1)));
  }
  return 0;
}
