#include <bits/stdc++.h>
using namespace std;
int t, n;
long long S[105], x, y, z, X[105], Y[105], F[5][105];
int Q(int n, long long x, long long y) {
  if (x == y) return 0;
  if (n == 1) return x != y;
  if (x == 1 && y == S[n]) return n + 1 >> 1;
  int p = 4;
  if (x == 1)
    p = y == Y[n];
  else if (y == S[n])
    p = 2 + (x == Y[n]);
  if (~F[p][n]) return F[p][n];
  if (y <= S[n - 1])
    F[p][n] = min(Q(n - 1, x, y), Q(n - 1, 1, x) + Q(n - 1, y, S[n - 1]) + 2);
  else if (x > S[n - 1])
    F[p][n] = Q(n - 2, x - S[n - 1], y - S[n - 1]);
  else
    F[p][n] = min(Q(n - 1, 1, x), Q(n - 1, x, S[n - 1])) + 1 +
              Q(n - 2, 1, y - S[n - 1]);
  return F[p][n];
}
int main() {
  scanf("%d%d", &t, &n);
  S[0] = 1;
  S[1] = 2;
  for (int i = 2; i <= 80; ++i) S[i] = S[i - 1] + S[i - 2];
  while (t--) {
    scanf("%lld%lld", &x, &y);
    memset(F, -1, sizeof F);
    if (x > y) swap(x, y);
    n = min(n, 80);
    z = x;
    for (int i = n; i > 1;) {
      X[i] = z;
      if (z > S[i - 1])
        X[i - 1] = 0, z -= S[i - 1], i -= 2;
      else
        --i;
    }
    z = y;
    for (int i = n; i > 1;) {
      Y[i] = z;
      if (z > S[i - 1])
        Y[i - 1] = 0, z -= S[i - 1], i -= 2;
      else
        --i;
    }
    printf("%d\n", Q(n, x, y));
  }
  return 0;
}
