#include <bits/stdc++.h>
using namespace std;
long long solve(const vector<long long>& D, int N, long long a, long long b) {
  N = min<int>(D.size() - 1, N);
  vector<long long> aa(N + 1, -1), bb(N + 1, -1);
  aa[N] = a;
  bb[N] = b;
  for (int n = N; n >= 2; --n) {
    if (aa[n] != -1)
      if (aa[n] <= D[n - 1])
        aa[n - 1] = aa[n];
      else
        aa[n - 2] = aa[n] - D[n - 1];
    if (bb[n] != -1)
      if (bb[n] <= D[n - 1])
        bb[n - 1] = bb[n];
      else
        bb[n - 2] = bb[n] - D[n - 1];
  }
  vector<long long> d1X(N + 1), d1a(N + 1), d1b(N + 1), daX(N + 1), dbX(N + 1);
  for (int n = 0; n <= N; ++n) {
    if (n == 0)
      d1X[n] = 0;
    else if (n == 1)
      d1X[n] = 1;
    else
      d1X[n] = 1 + d1X[n - 2];
    long long a = aa[n];
    if (a != -1) {
      if (n == 0)
        d1a[n] = 0, daX[n] = 0;
      else if (n == 1)
        d1a[n] = (a == 1 ? 0 : 1), daX[n] = (a == 1 ? 1 : 0);
      else {
        if (a <= D[n - 1])
          d1a[n] = min(d1a[n - 1], daX[n - 1] + 2);
        else
          d1a[n] = d1a[n - 2] + 1;
        if (a <= D[n - 1])
          daX[n] = min(d1a[n - 1], daX[n - 1]) + 1 + d1X[n - 2];
        else
          daX[n] = daX[n - 2];
      }
    }
    long long b = bb[n];
    if (b != -1) {
      if (n == 0)
        d1b[n] = 0, dbX[n] = 0;
      else if (n == 1)
        d1b[n] = (b == 1 ? 0 : 1), dbX[n] = (b == 1 ? 1 : 0);
      else {
        if (b <= D[n - 1])
          d1b[n] = min(d1b[n - 1], dbX[n - 1] + 2);
        else
          d1b[n] = d1b[n - 2] + 1;
        if (b <= D[n - 1])
          dbX[n] = min(d1b[n - 1], dbX[n - 1]) + 1 + d1X[n - 2];
        else
          dbX[n] = dbX[n - 2];
      }
    }
  }
  long long cand = 10000000000000000LL;
  for (;;) {
    if (a == b) {
      cand = min(cand, 0LL);
      break;
    }
    if (N == 1) {
      cand = min(cand, 1LL);
      break;
    }
    if (a <= D[N - 1] && b <= D[N - 1]) {
      cand = min(cand, d1a[N - 1] + 2 + dbX[N - 1]);
      cand = min(cand, d1b[N - 1] + 2 + daX[N - 1]);
      N = N - 1;
    } else if (a > D[N - 1] && b > D[N - 1]) {
      a = a - D[N - 1];
      b = b - D[N - 1];
      N = N - 2;
    } else {
      cand = min(cand, min(d1a[N - 1], daX[N - 1]) + 1 + d1b[N - 2]);
      break;
    }
  }
  return cand;
}
int main() {
  vector<long long> D = {1, 2};
  while (D.back() < 50000000000000000LL)
    D.push_back(D[D.size() - 1] + D[D.size() - 2]);
  for (int T, N; cin >> T >> N;) {
    for (int i = 0; i < T; ++i) {
      long long a, b;
      cin >> a >> b;
      if (a > b) swap(a, b);
      cout << solve(D, N, a, b) << endl;
    }
  }
}
