#include <bits/stdc++.h>
using namespace std;
const int MAX_ = 100;
vector<long long> D, Le;
int n, t;
void solve(long long x, long long X[MAX_][2]) {
  int q[MAX_], s = 0;
  long long ind[MAX_];
  ind[s] = x;
  q[s++] = n;
  long long y = x;
  X[0][0] = X[0][1] = 0;
  for (int k = n; k >= 1;) {
    if (k == 1) {
      if (y == 1) {
        X[1][0] = 0;
        X[1][1] = 1;
      } else {
        X[1][0] = 1;
        X[1][1] = 0;
      }
      break;
    }
    if (y <= D[k - 1]) {
      ind[s] = y;
      q[s++] = k - 1;
      k--;
    } else {
      y -= D[k - 1];
      ind[s] = y;
      q[s++] = k - 2;
      k -= 2;
    }
  }
  for (int i = s - 1; i >= 0; i--) {
    if (q[i] <= 1) continue;
    if (ind[i] <= D[q[i] - 1]) {
      X[q[i]][0] = X[q[i] - 1][1] + 2;
      if (X[q[i] - 1][0] <= X[q[i]][0]) X[q[i]][0] = X[q[i] - 1][0];
      X[q[i]][1] = X[q[i] - 1][0];
      if (X[q[i] - 1][1] < X[q[i]][1]) X[q[i]][1] = X[q[i] - 1][1];
      X[q[i]][1] += 1 + Le[q[i] - 2];
    } else {
      X[q[i]][1] = X[q[i] - 2][1];
      X[q[i]][0] = X[q[i] - 2][0] + 1;
    }
  }
}
long long A[MAX_][2], B[MAX_][2];
int main() {
  cin >> t >> n;
  D.push_back(1);
  Le.push_back(0);
  D.push_back(2);
  Le.push_back(1);
  while (1) {
    long long cur = D.back() + D[(int)D.size() - 2];
    if (cur > (long long)(1000 * 1000 * 1000) * (long long)(1000 * 1000 * 30)) {
      n = (int)D.size() - 1;
      break;
    }
    if (((int)D.size()) == (n + 1)) break;
    Le.push_back(1 + Le[(int)Le.size() - 2]);
    D.push_back(cur);
  }
  for (int TE = 0; TE < t; TE++) {
    long long a, b;
    cin >> a >> b;
    if (b < a) swap(a, b);
    solve(a, A);
    solve(b, B);
    long long Ans =
        (long long)(1000 * 1000 * 1000) * (long long)(1000 * 1000 * 1000);
    for (int k = n; k >= 1;) {
      if (k == 1) {
        Ans = 1;
        break;
      }
      bool ta = 0, tb = 0;
      if (a <= D[k - 1])
        ta = 0;
      else
        ta = 1;
      if (b <= D[k - 1])
        tb = 0;
      else
        tb = 1;
      if (ta && tb) {
        a -= D[k - 1];
        b -= D[k - 1];
        k -= 2;
      } else if (!ta && !tb) {
        long long Cur1 = A[k - 1][0] + B[k - 1][1] + 2;
        long long Cur2 = A[k - 1][1] + B[k - 1][0] + 2;
        long long Cur = (Cur1 < Cur2 ? Cur1 : Cur2);
        if (Cur < Ans) Ans = Cur;
        k--;
      } else {
        long long Cur = A[k - 1][0];
        if (A[k - 1][1] < Cur) Cur = A[k - 1][1];
        Cur = Cur + 1 + B[k - 2][0];
        if (Cur < Ans) {
          Ans = Cur;
        }
        break;
      }
    }
    cout << Ans;
    cout << endl;
  }
  return 0;
}
