#include <bits/stdc++.h>
using namespace std;
const int maxn = 1005;
long long f[maxn];
long long First[2][maxn];
long long Last[2][maxn];
int T, N;
long long first(long long a, int type, int n);
long long last(long long a, int type, int n);
long long first(long long a, int type, int n) {
  if (First[type][n] != -1) return First[type][n];
  if (n == 0) return First[type][0] = 0;
  if (n == 1) return First[type][0] = (a == 1 ? 0 : 1);
  if (a <= f[n - 1]) {
    long long d1 = first(a, type, n - 1);
    long long d2 = last(a, type, n - 1) + 2;
    return First[type][n] = min(d1, d2);
  } else {
    return First[type][n] = first(a - f[n - 1], type, n - 2) + 1;
  }
}
long long last(long long a, int type, int n) {
  if (Last[type][n] != -1) return Last[type][n];
  if (n == 0) return Last[type][0] = 0;
  if (n == 1) return Last[type][0] = (a == 2 ? 0 : 1);
  if (a <= f[n - 1]) {
    long long d1 = first(a, type, n - 1) + 1 + (n - 1) / 2;
    long long d2 = last(a, type, n - 1) + 1 + (n - 1) / 2;
    return Last[type][n] = min(d1, d2);
  } else {
    return Last[type][n] = last(a - f[n - 1], type, n - 2);
  }
}
long long dfs(long long a, long long b, int n) {
  if (a > b) swap(a, b);
  if (a == b) return 0;
  if (n == 0) return 0;
  if (n == 1) return 1;
  if (b <= f[n - 1]) {
    long long d1 = dfs(a, b, n - 1);
    long long d2 = first(a, 0, n - 1) + last(b, 1, n - 1) + 2;
    long long d3 = last(a, 0, n - 1) + first(b, 1, n - 1) + 2;
    return min(d1, min(d2, d3));
  }
  if (a > f[n - 1]) {
    return dfs(a - f[n - 1], b - f[n - 1], n - 2);
  }
  {
    long long d1 = first(a, 0, n - 1) + first(b - f[n - 1], 1, n - 2) + 1;
    long long d2 = last(a, 0, n - 1) + first(b - f[n - 1], 1, n - 2) + 1;
    return min(d1, d2);
  }
}
int main() {
  cin >> T >> N;
  f[0] = 1;
  f[1] = 2;
  f[2] = 3;
  N = min(N, 90);
  for (int i = 3; i <= N; i++) {
    f[i] = f[i - 1] + f[i - 2];
  }
  for (int i = 0; i < T; i++) {
    long long a, b;
    scanf("%I64d%I64d", &a, &b);
    for (int i = 0; i <= N; i++) {
      for (int j = 0; j < 2; j++) {
        First[j][i] = -1;
        Last[j][i] = -1;
      }
    }
    cout << dfs(a, b, N) << endl;
  }
  return 0;
}
