#include <bits/stdc++.h>
using namespace std;
int a1[1002], a2[1002], b1[1002], b2[1002], g[1002];
long long f[1002];
void work(long long u, int n, int* d1, int* d2) {
  if (n == 0) {
    d1[n] = d2[n] = 0;
    return;
  }
  if (n == 1) {
    if (u == 1)
      d1[n] = 0, d2[n] = 1;
    else
      d1[n] = 1, d2[n] = 0;
    return;
  }
  if (u <= f[n - 1]) {
    work(u, n - 1, d1, d2);
    d1[n] = min(d1[n - 1], d2[n - 1] + 2);
    d2[n] = min(d1[n - 1], d2[n - 1]) + 1 + g[n - 2];
  } else {
    work(u - f[n - 1], n - 2, d1, d2);
    d2[n] = d2[n - 2];
    d1[n] = d1[n - 2] + 1;
  }
}
void init(int n) {
  g[0] = 0, g[1] = 1;
  for (int i = 2; i <= n; ++i) g[i] = g[i - 2] + 1;
}
int find(long long a, long long b, int n) {
  if (n <= 0) return 0;
  int ans;
  if (a <= f[n - 1] && b > f[n - 1])
    ans = min(a1[n - 1], a2[n - 1]) + 1 + b1[n - 2];
  else if (a <= f[n - 1] && b <= f[n - 1])
    ans = min(find(a, b, n - 1),
              min(a1[n - 1] + 2 + b2[n - 1], a2[n - 1] + 2 + b1[n - 1]));
  else
    ans = find(a - f[n - 1], b - f[n - 1], n - 2);
  return ans;
}
int main() {
  int t, n, ans;
  long long a, b;
  scanf("%d%d\n", &t, &n);
  if (n >= 80) n = 80;
  f[0] = 1, f[1] = 2;
  for (int i = 2; i <= n; ++i) f[i] = f[i - 1] + f[i - 2];
  init(n);
  for (int i = 1; i <= t; ++i) {
    scanf(
        "%I64d"
        "%I64d",
        &a, &b);
    if (a > b) swap(a, b);
    if (n == 1) {
      printf("%d\n", a == b ? 0 : 1);
      continue;
    }
    work(a, n, a1, a2);
    work(b, n, b1, b2);
    ans = find(a, b, n);
    printf("%d\n", ans);
  }
  return 0;
}
