#include <bits/stdc++.h>
using namespace std;
struct ans {
  long long k;
  int val;
  bool operator<(const ans& o) const { return k < o.k; }
  ans(long long k, int val) : k(k), val(val) {}
};
long long aa, bb;
long long cnt[1010];
long long A[2][100], B[2][100];
long long D[100];
long long inline findDist(int n, long long a, long long b, int callForm) {
  if (a == b) return 0;
  if (n <= 2) return 1;
  if (a == 1 && b == cnt[n] && D[n] != -1) return D[n];
  if (a == 1) {
    if (callForm == 1)
      if (A[0][n] != -1) return A[0][n];
    if (callForm == 2)
      if (B[0][n] != -1) return B[0][n];
  }
  if (b == cnt[n]) {
    if (callForm == 1)
      if (A[1][n] != -1) return A[1][n];
    if (callForm == 2)
      if (B[1][n] != -1) return B[1][n];
  }
  long long ret;
  if (a > b) swap(a, b);
  if (a == 1 && b < 5) return 1;
  if (a > cnt[n - 1]) {
    ret = findDist(n - 2, a - cnt[n - 1], b - cnt[n - 1], callForm);
  } else if (b <= cnt[n - 1]) {
    ret = min(findDist(n - 1, a, b, callForm),
              2 +
                  min(findDist(n - 1, 1, b, callForm ? callForm : 2),
                      findDist(n - 1, b, cnt[n - 1], callForm ? callForm : 2)) +
                  min(findDist(n - 1, 1, a, callForm ? callForm : 1),
                      findDist(n - 1, a, cnt[n - 1], callForm ? callForm : 1)));
  } else {
    ret = findDist(n - 2, 1, b - cnt[n - 1], callForm ? callForm : 2) + 1 +
          min(findDist(n - 1, 1, a, callForm ? callForm : 1),
              findDist(n - 1, a, cnt[n - 1], callForm ? callForm : 1));
  }
  if (a == 1) {
    if (callForm == 1) A[0][n] = ret;
    if (callForm == 2) B[0][n] = ret;
  }
  if (b == cnt[n]) {
    if (callForm == 1) A[1][n] = ret;
    if (callForm == 2) B[1][n] = ret;
  }
  if (a == 1 && b == cnt[n]) D[n] = ret;
  return ret;
}
int maxN = 80;
int main() {
  cnt[0] = 1;
  cnt[1] = 2;
  for (int i = 2; i <= 100; i++) {
    cnt[i] = cnt[i - 1] + cnt[i - 2];
  }
  memset(D, -1, sizeof(D));
  D[0] = 0;
  D[1] = 1;
  for (int i = 2; i <= 100; i++) D[i] = 1 + D[i - 2];
  int t, n;
  scanf("%d %d", &t, &n);
  if (n > maxN) n = maxN;
  for (int i = 0; i < t; i++) {
    memset(A, -1, sizeof(A));
    memset(B, -1, sizeof(B));
    scanf("%I64d %I64d", &aa, &bb);
    int k = 3;
    while (max(aa, bb) >= cnt[k]) k++;
    k += 2;
    if (k > n) k = n;
    printf("%I64d\n", findDist(k, aa, bb, 0));
  }
}
