#include <bits/stdc++.h>
using namespace std;
const int N = 1003;
long long D[N];
int val[2][N][2];
long long id[2][N][2];
int ed[N];
int calc(int q, long long a, int n, int k) {
  if (n == 0) return 0;
  if (n == 1) return a != k + 1;
  if (id[q][n][k] == a) return val[q][n][k];
  id[q][n][k] = a;
  if (k == 0) {
    if (a <= D[n - 1])
      val[q][n][k] = min(calc(q, a, n - 1, 0), calc(q, a, n - 1, 1) + 2);
    else
      val[q][n][k] = calc(q, a - D[n - 1], n - 2, 0) + 1;
  } else {
    if (a <= D[n - 1])
      val[q][n][k] =
          min(calc(q, a, n - 1, 0), calc(q, a, n - 1, 1)) + 1 + ed[n - 2];
    else
      val[q][n][k] = calc(q, a - D[n - 1], n - 2, 1);
  }
  return val[q][n][k];
}
int query(long long a, long long b, int n) {
  if (n == 1) return 1;
  if (b <= D[n - 1]) {
    int x = min(calc(0, a, n - 1, 0) + calc(1, b, n - 1, 1) + 2,
                calc(0, a, n - 1, 0) + calc(1, b, n - 1, 0) + 2);
    return min(x, query(a, b, n - 1));
  }
  if (a <= D[n - 1])
    return min(calc(0, a, n - 1, 0), calc(0, a, n - 1, 1)) + 1 +
           calc(1, b - D[n - 1], n - 2, 0);
  return query(a - D[n - 1], b - D[n - 1], n - 2);
}
int main() {
  D[0] = 1;
  D[1] = 2;
  ed[0] = 0;
  ed[1] = 1;
  for (int i = 2; i < 78; ++i) {
    D[i] = D[i - 1] + D[i - 2];
    ed[i] = ed[i - 2] + 1;
  }
  for (int i = 78; i < N; ++i) D[i] = D[i - 1];
  int t, n;
  scanf("%d%d", &t, &n);
  if (n > 85) n = 85;
  while (t--) {
    long long a, b;
    scanf("%lld%lld", &a, &b);
    if (a == b) {
      puts("0");
      continue;
    }
    if (a > b) swap(a, b);
    printf("%d\n", query(a, b, n));
  }
  return 0;
}
