#include <bits/stdc++.h>
using namespace std;
const long long MAX = 9999999999999999;
int t, n;
vector<long long> ans;
vector<long long> graphSize;
vector<long long> aToFirst, aToLast, bToFirst, bToLast;
void countLength(vector<long long> &toFirst, vector<long long> &toLast,
                 long long v, int n) {
  if (n == 0) {
    toFirst[0] = 0;
    toLast[0] = 0;
    return;
  }
  if (n == 1) {
    toFirst[1] = v == 2;
    toLast[1] = v == 1;
    return;
  }
  if (v <= graphSize[n - 1]) {
    countLength(toFirst, toLast, v, n - 1);
    toFirst[n] = min(toFirst[n - 1], toLast[n - 1] + 2);
    toLast[n] = min(toFirst[n - 1], toLast[n - 1]) + (n - 1) / 2 + 1;
  } else {
    countLength(toFirst, toLast, v - graphSize[n - 1], n - 2);
    toFirst[n] = toFirst[n - 2] + 1;
    toLast[n] = toLast[n - 2];
  }
}
long long findMinLength(long long a, long long b, int n) {
  if (a == b) return 0;
  if (n <= 2) return 1;
  if (a <= graphSize[n - 1]) {
    if (b >= graphSize[n - 1] + 1) {
      return min(aToFirst[n - 1], aToLast[n - 1]) + bToFirst[n - 2] + 1;
    } else {
      long long d1 = min(aToFirst[n - 1] + bToLast[n - 1] + 2,
                         aToLast[n - 1] + bToFirst[n - 1] + 2);
      return min(d1, findMinLength(a, b, n - 1));
    }
  } else {
    return findMinLength(a - graphSize[n - 1], b - graphSize[n - 1], n - 2);
  }
}
int main() {
  cin >> t >> n;
  graphSize.push_back(1);
  graphSize.push_back(2);
  int iMax = 2;
  for (; graphSize.back() < MAX; ++iMax) {
    graphSize.push_back(graphSize[iMax - 1] + graphSize[iMax - 2]);
  }
  for (int i = 1; i <= t; ++i) {
    long long a, b;
    cin >> a >> b;
    if (a > b) swap(a, b);
    aToFirst.resize(min(n, iMax) + 1);
    aToLast.resize(min(n, iMax) + 1);
    bToFirst.resize(min(n, iMax) + 1);
    bToLast.resize(min(n, iMax) + 1);
    countLength(aToFirst, aToLast, a, min(n, iMax));
    countLength(bToFirst, bToLast, b, min(n, iMax));
    ans.push_back(findMinLength(a, b, min(n, iMax)));
  }
  for (int i = 0; i < ans.size(); ++i) {
    cout << ans[i] << endl;
  }
  return 0;
}
