#include <bits/stdc++.h>
using namespace std;
inline long long read() {
  register long long x(0), f(1);
  register char c(getchar());
  while (c > '9' || c < '0') f = c == '-' ? -1 : 1, c = getchar();
  while (c <= '9' && c >= '0') x = x * 10 + c - 48, c = getchar();
  return x * f;
}
const int N = 1010;
int n, m;
long long d[N], g[N], a1[N], a2[N], b1[N], b2[N];
void work(long long x, long long n, long long c1[], long long c2[]) {
  if (n == 0) {
    c1[n] = c2[n] = 0;
    return;
  }
  if (n == 1) {
    c1[n] = (x == 2);
    c2[n] = (x == 1);
    return;
  }
  if (x <= d[n - 1]) {
    work(x, n - 1, c1, c2);
    c1[n] = min(c1[n - 1], c2[n - 1] + 2);
    c2[n] = min(c1[n - 1], c2[n - 1]) + 1 + g[n - 2];
  } else {
    work(x - d[n - 1], n - 2, c1, c2);
    c1[n] = c1[n - 2] + 1;
    c2[n] = c2[n - 2];
  }
}
long long dis(long long u, long long v, int n) {
  if (n <= 1) return u != v;
  if (u <= d[n - 1]) {
    if (v > d[n - 1])
      return min(a1[n - 1], a2[n - 1]) + 1 + b1[n - 2];
    else
      return min(dis(u, v, n - 1),
                 min(a1[n - 1] + b2[n - 1], a2[n - 1] + b1[n - 1]) + 2);
  } else
    return dis(u - d[n - 1], v - d[n - 1], n - 2);
}
int main() {
  m = read(), n = read();
  n = min(n, 77);
  d[0] = 1, d[1] = 2;
  for (int i = 2; i <= n; ++i) d[i] = d[i - 1] + d[i - 2];
  g[0] = 0;
  g[1] = g[2] = 1;
  for (int i = 3; i <= n; i++) g[i] = g[i - 2] + 1;
  while (m--) {
    long long u = read(), v = read();
    if (u > v) swap(u, v);
    work(u, n, a1, a2);
    work(v, n, b1, b2);
    cout << dis(u, v, n) << '\n';
  }
  return 0;
}
