#include <bits/stdc++.h>
const int N = 100010;
const int inf = 0x3f3f3f3f;
using namespace std;
int n, t;
long long a, b, f[N];
int dp1[110][2], dp2[110][2];
int dfs1(int a, int b, long long c) {
  if (a == 1) return c + b == 2;
  if (a == 0) return 0;
  int &ret = dp1[a][b];
  if (ret + 1) return dp1[a][b];
  if (b) {
    if (c > f[a - 1])
      ret = dfs1(a - 2, 1, c - f[a - 1]);
    else
      ret = min(dfs1(a - 1, 1, c), dfs1(a - 1, 0, c)) + 1 + (a - 1) / 2;
  } else {
    if (c > f[a - 1])
      ret = dfs1(a - 2, 0, c - f[a - 1]) + 1;
    else
      ret = min(dfs1(a - 1, 0, c), dfs1(a - 1, 1, c) + 2);
  }
  return ret;
}
int dfs2(int a, int b, long long c) {
  if (a == 1) return c + b == 2;
  if (a == 0) return 0;
  int &ret = dp2[a][b];
  if (ret + 1) return ret;
  if (b) {
    if (c > f[a - 1])
      ret = dfs2(a - 2, 1, c - f[a - 1]);
    else
      ret = min(dfs2(a - 1, 1, c), dfs2(a - 1, 0, c)) + 1 + (a - 1) / 2;
  } else {
    if (c > f[a - 1])
      ret = dfs2(a - 2, 0, c - f[a - 1]) + 1;
    else
      ret = min(dfs2(a - 1, 0, c), dfs2(a - 1, 1, c) + 2);
  }
  return ret;
}
int dfs(long long a, long long b, int k) {
  if (a == b) return 0;
  if (k == 1) return 1;
  if (a > f[k - 1] && b > f[k - 1])
    return dfs(a - f[k - 1], b - f[k - 1], k - 2);
  if (a <= f[k - 1] && b <= f[k - 1]) {
    int ret = dfs(a, b, k - 1);
    ret = min(ret, dfs1(k - 1, 0, a) + dfs2(k - 1, 1, b) + 2);
    ret = min(ret, dfs1(k - 1, 1, a) + dfs2(k - 1, 0, b) + 2);
    return ret;
  }
  return min(dfs1(k - 1, 1, a), dfs1(k - 1, 0, a)) +
         dfs2(k - 2, 0, b - f[k - 1]) + 1;
}
int main() {
  cin >> t >> n;
  if (n > 90) n = 90;
  f[0] = 1;
  f[1] = 2;
  for (int i = 2; i <= 91; i++) f[i] = f[i - 1] + f[i - 2];
  for (int i = 0; i < t; i++) {
    cin >> a >> b;
    memset(dp1, -1, sizeof(dp1));
    memset(dp2, -1, sizeof(dp2));
    if (a > b) swap(a, b);
    cout << dfs(a, b, n) << endl;
  }
  return 0;
}
