#include <bits/stdc++.h>
using namespace std;
const int MAX = 1000;
const long long MAXD = 10000000000000000LL;
long long D[MAX], tot;
long long t, n;
int dp[MAX][5];
long long key[MAX][2];
inline int dist(long long a, long long b, int n) {
  if (a > b) swap(a, b);
  if (a == b) return 0;
  if (n == 1 || n == 2) return 1;
  int idx = -1, ans;
  long long V = D[n];
  if (a == 1) {
    if (b == V)
      idx = 0;
    else if (b == key[n][0])
      idx = 1;
    else if (b == key[n][1])
      idx = 2;
  } else if (b == V) {
    if (a == key[n][0])
      idx = 3;
    else if (a == key[n][1])
      idx = 4;
  }
  if (idx != -1 && dp[n][idx] != -1) return dp[n][idx];
  long long U = D[n - 1];
  if (a <= U && b >= U + 1) {
    int d = min(dist(1, a, n - 1), dist(a, U, n - 1));
    ans = d + dist(1, b - U, n - 2) + 1;
  } else if (a >= D[n - 1] + 1)
    ans = dist(a - U, b - U, n - 2);
  else {
    int d1 = dist(a, b, n - 1);
    int d2 = min(dist(1, a, n - 1), dist(a, U, n - 1));
    int d3 = min(dist(1, b, n - 1), dist(b, U, n - 1));
    ans = min(d1, d2 + d3 + 2);
  }
  if (idx != -1) dp[n][idx] = ans;
  return ans;
}
int main() {
  long long a, b, i, j, k, aa, bb;
  for (D[0] = 1, D[1] = 2, i = 2;; ++i) {
    D[i] = D[i - 1] + D[i - 2];
    if (D[i] > MAXD) break;
    tot = i;
  }
  cin >> t >> n;
  n = min(i, n);
  for (i = 1; i <= t; ++i) {
    cin >> a >> b;
    if (a > b) swap(a, b);
    for (aa = a, bb = b, j = n; j >= 0; --j) {
      if (aa > D[j]) aa -= D[j];
      if (bb > D[j]) bb -= D[j];
      key[j][0] = aa;
      key[j][1] = bb;
      for (k = 0; k <= 4; ++k) dp[j][k] = -1;
    }
    cout << dist(a, b, n) << endl;
  }
}
