#include <bits/stdc++.h>
using namespace std;
const int maxn = 100;
int m, n;
long long f[maxn], dis[2][2][maxn];
void dfs(const int k, const int s, const long long x) {
  if (s == 0) return;
  if (s == 1) {
    dis[k][0][s] = (x == 1 ? 0 : 1);
    dis[k][1][s] = (x == 2 ? 0 : 1);
    return;
  }
  if (x <= f[s - 1]) {
    dfs(k, s - 1, x);
    dis[k][0][s] = min(dis[k][0][s - 1], dis[k][1][s - 1] + 2);
    dis[k][1][s] = min(dis[k][0][s - 1], dis[k][1][s - 1]) + ((s + 1) >> 1);
  } else {
    dfs(k, s - 2, x - f[s - 1]);
    dis[k][0][s] = dis[k][0][s - 2] + 1;
    dis[k][1][s] = dis[k][1][s - 2];
  }
}
long long solve(const long long x, const long long y, const int s) {
  if (x == y) return 0;
  if (y <= f[s - 1])
    return min(solve(x, y, s - 1), dis[0][0][s - 1] + dis[1][1][s - 1] + 2);
  if (x <= f[s - 1] && y > f[s - 1])
    return min(dis[0][0][s - 1], dis[0][1][s - 1]) + dis[1][0][s - 2] + 1;
  if (x > f[s - 1]) return solve(x - f[s - 1], y - f[s - 1], s - 2);
}
int main() {
  scanf("%d%d", &m, &n);
  n = min(n, 80);
  f[0] = 1;
  f[1] = 2;
  for (int i = 2; i <= n; ++i) f[i] = f[i - 1] + f[i - 2];
  long long x, y;
  for (int i = 1; i <= m; ++i) {
    scanf("%I64d%I64d", &x, &y);
    if (x > y) swap(x, y);
    memset(dis, 0, sizeof(dis));
    dfs(0, n, x);
    dfs(1, n, y);
    printf("%I64d\n", solve(x, y, n));
  }
  return 0;
}
