#include <bits/stdc++.h>
using namespace std;
const int mn = 105;
const long long inf = (1LL << 60);
int g[mn];
long long f[mn], x, y, a1[mn], a2[mn], b1[mn], b2[mn];
void pre(long long x, int num, long long *d1, long long *d2) {
  if (num == 0) {
    d1[num] = d2[num] = 0;
    return;
  } else if (num == 1) {
    d1[num] = (x == 2);
    d2[num] = (x == 1);
    return;
  }
  if (x <= f[num - 1]) {
    pre(x, num - 1, d1, d2);
    d1[num] = min(d1[num - 1], d2[num - 1] + 2);
    d2[num] = min(d2[num - 1], d1[num - 1]) + 1 + g[num - 2];
  } else {
    pre(x - f[num - 1], num - 2, d1, d2);
    d1[num] = d1[num - 2] + 1;
    d2[num] = d2[num - 2];
  }
}
long long work(long long x, long long y, long long s) {
  if (s <= 1) return (x != y);
  if (x <= f[s - 1]) {
    if (y > f[s - 1])
      return min(a1[s - 1], a2[s - 1]) + b1[s - 2] + 1;
    else
      return min(work(x, y, s - 1),
                 min(a1[s - 1] + b2[s - 1], a2[s - 1] + b1[s - 1]) + 2);
  } else
    return work(x - f[s - 1], y - f[s - 1], s - 2);
}
int n, m;
int main() {
  scanf("%d%d", &m, &n);
  if (n >= 80) n = 80;
  f[1] = 2, f[2] = 3;
  for (int i = 3; i <= n; i++) f[i] = f[i - 1] + f[i - 2];
  g[0] = 0, g[1] = g[2] = 1;
  for (int i = 3; i <= n; i++) g[i] = g[i - 2] + 1;
  for (int i = 1; i <= m; i++) {
    scanf("%lld%lld", &x, &y);
    if (x > y) swap(x, y);
    pre(x, n, a1, a2);
    pre(y, n, b1, b2);
    printf("%lld\n", work(x, y, n));
  }
  return 0;
}
