#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 9;
long long d[N], g[N], a1[N], a2[N], b1[N], b2[N], n;
int m;
void Init() {
  n = min(n, 80ll);
  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] = 1;
  for (int i = 2; i <= n; i++) g[i] = g[i - 2] + 1;
}
void find(long long u, long long n, long long *c1, long long *c2) {
  if (n == 0) {
    c1[n] = c2[n] = 0;
    return;
  }
  if (n == 1) {
    c1[n] = (u != 1), c2[n] = (u != 2);
    return;
  }
  if (u <= d[n - 1]) {
    find(u, 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 {
    find(u - d[n - 1], n - 2, c1, c2);
    c1[n] = c1[n - 2] + 1;
    c2[n] = c2[n - 2];
  }
}
long long dis(long long a, long long b, long long n) {
  if (n <= 1) return a != b;
  if (a <= d[n - 1])
    if (b <= d[n - 1])
      return min(min(a1[n - 1] + b2[n - 1], a2[n - 1] + b1[n - 1]) + 2,
                 dis(a, b, n - 1));
    else
      return min(a1[n - 1], a2[n - 1]) + b1[n - 2] + 1;
  return dis(a - d[n - 1], b - d[n - 1], n - 2);
}
int main() {
  scanf("%d%lld", &m, &n);
  Init();
  while (m--) {
    long long a, b;
    scanf("%lld%lld", &a, &b);
    if (a > b) swap(a, b);
    find(a, n, a1, a2);
    find(b, n, b1, b2);
    printf("%lld\n", dis(a, b, n));
  }
  return 0;
}
