#include <bits/stdc++.h>
using namespace std;
const long long INF = (long long)1e16;
long long fib[1005], begs[2][1005], endss[2][1005], diam[1005];
void find_dist(int num, int typ, long long a) {
  if (num == 0) {
    begs[typ][0] = 0, endss[typ][0] = 0;
    return;
  }
  if (num == 1) {
    if (a == 1)
      begs[typ][1] = 0, endss[typ][1] = 1;
    else
      begs[typ][1] = 1, endss[typ][1] = 0;
    return;
  }
  if (a <= fib[num - 1]) {
    find_dist(num - 1, typ, a);
    begs[typ][num] = min(begs[typ][num - 1], endss[typ][num - 1] + 2);
    endss[typ][num] =
        min(begs[typ][num - 1], endss[typ][num - 1]) + 1 + diam[num - 2];
  } else {
    find_dist(num - 2, typ, a - fib[num - 1]);
    begs[typ][num] = begs[typ][num - 2] + 1;
    endss[typ][num] = endss[typ][num - 2];
  }
  return;
}
long long find_path(int num, long long a, long long b) {
  if (num == 0) return 0;
  if (num == 1) return (a != b);
  if (a <= fib[num - 1] && b <= fib[num - 1]) {
    long long t = find_path(num - 1, a, b);
    return min(t, min(begs[0][num - 1] + 2 + endss[1][num - 1],
                      begs[1][num - 1] + 2 + endss[0][num - 1]));
  }
  if (a > fib[num - 1] && b > fib[num - 1])
    return find_path(num - 2, a - fib[num - 1], b - fib[num - 1]);
  if (a <= fib[num - 1])
    return min(begs[0][num - 1], endss[0][num - 1]) + 1 + begs[1][num - 2];
  else
    return min(begs[1][num - 1], endss[1][num - 1]) + 1 + begs[0][num - 2];
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int test, n, uk = 1;
  cin >> test >> n;
  fib[0] = 1, fib[1] = 2;
  diam[0] = 0, diam[1] = 1;
  while (true) {
    uk++;
    fib[uk] = fib[uk - 1] + fib[uk - 2];
    diam[uk] = 1 + diam[uk - 2];
    if (fib[uk - 1] >= INF) break;
  }
  int start = min(n, uk);
  for (int rep = 1; rep <= test; rep++) {
    long long a, b;
    cin >> a >> b;
    find_dist(start, 0, a);
    find_dist(start, 1, b);
    cout << find_path(start, a, b) << '\n';
  }
  return 0;
}
