#include <bits/stdc++.h>
using namespace std;
int n, m;
const int maxn = 1e3 + 10;
long long c[maxn], g[maxn], a1[maxn], a2[maxn], b1[maxn], b2[maxn];
long long mn(long long a, long long b) { return a < b ? a : b; }
int mint(int a, int b) { return a < b ? a : b; }
void work(long long u, int v, long long *d1, long long *d2) {
  if (v == 0) {
    d1[v] = d2[v] = 0;
    return;
  }
  if (v == 1) {
    d1[v] = (u == 2);
    d2[v] = (u == 1);
    return;
  }
  if (u <= c[v - 1]) {
    work(u, v - 1, d1, d2);
    d1[v] = mn(d1[v - 1], d2[v - 1] + 2);
    d2[v] = mn(d2[v - 1], d1[v - 1]) + 1 + g[v - 2];
  } else {
    work(u - c[v - 1], v - 2, d1, d2);
    d1[v] = d1[v - 2] + 1;
    d2[v] = d2[v - 2];
  }
  return;
}
long long get_ans(long long u, long long v, int k) {
  if (k <= 1) return (u != v);
  if (u <= c[k - 1]) {
    if (v > c[k - 1])
      return mn(a1[k - 1], a2[k - 1]) + b1[k - 2] + 1;
    else
      return mn(get_ans(u, v, k - 1),
                mn(a1[k - 1] + b2[k - 1], b1[k - 1] + a2[k - 1]) + 2);
  } else
    return get_ans(u - c[k - 1], v - c[k - 1], k - 2);
}
int main() {
  cin >> m >> n;
  int i;
  n = mint(n, 80);
  c[0] = 1;
  c[1] = 2;
  for (i = 2; i <= n; i++) c[i] = c[i - 1] + c[i - 2];
  g[0] = 0;
  g[1] = g[2] = 1;
  for (i = 3; i <= n; i++) g[i] = g[i - 2] + 1;
  long long a, b, u, v;
  for (i = 1; i <= m; i++) {
    cin >> a >> b;
    v = a > b ? a : b;
    u = a < b ? a : b;
    work(u, n, a1, a2);
    work(v, n, b1, b2);
    cout << get_ans(u, v, n) << endl;
  }
  return 0;
}
