#include <bits/stdc++.h>
using namespace std;
inline long long read() {
  long long x = 0, f = 1;
  char c = getchar();
  while ((c < '0' || c > '9') && (c != '-')) c = getchar();
  if (c == '-') f = -1, c = getchar();
  while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
  return x * f;
}
const int N = 100, inf = 1e9;
int T, n;
long long f[N];
inline pair<int, int> dis2(long long u, int n, int d) {
  if (n <= 1) return make_pair(0, 0);
  if (u < f[n - 1]) {
    pair<int, int> tmp = dis2(u, n - 1, 2);
    return make_pair(tmp.first,
                     min(min(tmp.first, tmp.second) + n / 2, tmp.first + d));
  } else {
    pair<int, int> tmp = dis2(u - f[n - 1], n - 2, d + 1);
    return make_pair(min(tmp.first + 1, tmp.second + d), tmp.second);
  }
}
inline int dis(long long u, long long v, int n, int d) {
  if (u == 0 && v == f[n] - 1) return min(d, n / 2);
  if (v < f[n - 1]) return dis(u, v, n - 1, 2);
  if (u >= f[n - 1]) return dis(u - f[n - 1], v - f[n - 1], n - 2, d + 1);
  pair<int, int> a = dis2(u, n - 1, 2), b = dis2(v - f[n - 1], n - 2, d + 1);
  return min(min(a.first, a.second) + 1 + b.first, a.first + d + b.second);
}
int main() {
  T = read(), n = read(), n = min(n + 1, 80);
  f[0] = f[1] = 1;
  for (register int i = (2); i <= (n); i++) f[i] = f[i - 1] + f[i - 2];
  while (T--) {
    long long x = read(), y = read();
    if (x > y) swap(x, y);
    printf("%d\n", dis(x - 1, y - 1, n, inf));
  }
}
