#include <bits/stdc++.h>
using namespace std;
int n, nn, T, g[80][4][4];
long long f[80], p[80][4];
int work(int a, int b, int n) {
  if (n == -1 || p[n][a] == p[n][b]) return 0;
  if (g[n][a][b]) return g[n][a][b];
  int ans;
  if (p[n][a] > f[n - 1])
    ans = work(a, b, n - 2);
  else if (p[n][a] <= f[n - 1] && p[n][b] > f[n - 1])
    ans = min(work(0, a, n - 1), work(a, 3, n - 1)) + 1 + work(0, b, n - 2);
  else
    ans = min(work(a, b, n - 1), min(work(0, a, n - 1) + work(b, 3, n - 1),
                                     work(0, b, n - 1) + work(a, 3, n - 1)) +
                                     2);
  return g[n][a][b] = ans;
}
int main() {
  scanf("%d%d", &T, &nn);
  f[0] = 1;
  f[1] = 2;
  for (n = 2;; ++n) {
    f[n] = f[n - 1] + f[n - 2];
    if (f[n] > 1e16) break;
  }
  n = min(n, nn);
  while (T--) {
    long long x, y;
    scanf("%lld%lld", &x, &y);
    if (x > y) swap(x, y);
    for (int j = (int)(n); j >= (int)(0); j--) {
      p[j][0] = 1;
      p[j][3] = f[j];
      p[j][1] = x;
      p[j][2] = y;
      if (j && x > f[j - 1]) x -= f[j - 1];
      if (j && y > f[j - 1]) y -= f[j - 1];
      for (int k = (int)(0); k <= (int)(2); k++)
        for (int l = (int)(1); l <= (int)(3); l++) g[j][k][l] = 0;
      g[j][0][3] = (j + 1) / 2;
    }
    printf("%d\n", work(1, 2, n));
  }
}
