#include <bits/stdc++.h>
using namespace std;
long long fib[100];
long long First[100][2], Last[100][2];
long long first(int N, int type, long long x);
long long last(int N, int type, long long x);
long long first(int N, int type, long long x) {
  if (First[N][type] != -1) return First[N][type];
  if (N == 0) return First[N][type] = 0;
  if (N == 1) return First[N][type] = ((x == 0) ? 0 : 1);
  long long big = fib[N - 1];
  if (x < big) {
    long long d1 = first(N - 1, type, x);
    long long d2 = last(N - 1, type, x) + 2;
    return First[N][type] = min(d1, d2);
  }
  return First[N][type] = first(N - 2, type, x - big) + 1;
}
long long last(int N, int type, long long x) {
  if (Last[N][type] != -1) return Last[N][type];
  if (N == 0) return Last[N][type] = 0;
  if (N == 1) return Last[N][type] = ((x == 1) ? 0 : 1);
  long long big = fib[N - 1];
  if (x < big) {
    long long N2 = N - 2;
    long long tmp = (N2 + 1) / 2;
    long long d1 = first(N - 1, type, x) + 1 + tmp;
    long long d2 = last(N - 1, type, x) + 1 + tmp;
    return Last[N][type] = min(d1, d2);
  }
  return Last[N][type] = last(N - 2, type, x - big);
}
long long dfs(int N, long long x, long long y) {
  if (N == 0) return 0;
  if (N == 1) return ((x == y) ? 0 : 1);
  long long big = fib[N - 1];
  if (x < big && y < big) {
    long long d1 = dfs(N - 1, x, y);
    long long d2 = first(N - 1, 0, x) + last(N - 1, 1, y) + 2;
    long long d3 = first(N - 1, 1, y) + last(N - 1, 0, x) + 2;
    return min(d1, min(d2, d3));
  }
  if (x >= big && y >= big) {
    long long x2 = x - big, y2 = y - big;
    long long d1 = dfs(N - 2, x2, y2);
    return d1;
  }
  {
    long long x2 = x, y2 = y - big;
    long long d1 = first(N - 1, 0, x2) + first(N - 2, 1, y2) + 1;
    long long d2 = last(N - 1, 0, x2) + first(N - 2, 1, y2) + 1;
    return min(d1, d2);
  }
  return -1;
}
long long func(int N, long long x, long long y) {
  int i, j;
  if (x > y) swap(x, y);
  for ((i) = 0; (i) < (int)(N + 1); (i)++)
    for ((j) = 0; (j) < (int)(2); (j)++) First[i][j] = Last[i][j] = -1;
  long long ans = dfs(N, x, y);
  return ans;
}
int main(void) {
  int i;
  fib[0] = 1;
  fib[1] = 2;
  for (i = 2; i <= 90; i++) fib[i] = fib[i - 1] + fib[i - 2];
  int Q, N;
  cin >> Q >> N;
  N = min(N, 90);
  long long x, y;
  for ((i) = 0; (i) < (int)(Q); (i)++) {
    cin >> x >> y;
    x--;
    y--;
    long long ans = func(N, x, y);
    cout << ans << endl;
  }
  return 0;
}
