#include <bits/stdc++.h>
using namespace std;
int n, t, i, j, g[80][4][4], k, l;
long long f[80], a, b, 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) + 2,
                                   work(0, b, n - 1) + work(a, 3, n - 1) + 2));
  g[n][a][b] = ans;
  return ans;
}
int main() {
  scanf("%d%d", &t, &i);
  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, i);
  for (i = 1; i <= t; ++i) {
    scanf("%I64d%I64d", &a, &b);
    if (a > b) swap(a, b);
    for (j = n; j >= 0; --j) {
      p[j][0] = 1;
      p[j][1] = a;
      p[j][2] = b;
      p[j][3] = f[j];
      if (a > f[j - 1]) a -= f[j - 1];
      if (b > f[j - 1]) b -= f[j - 1];
      for (k = 0; k < 3; ++k)
        for (l = 1; l < 4; ++l) g[j][k][l] = 0;
      g[j][0][3] = (j + 1) / 2;
    }
    printf("%d\n", work(1, 2, n));
  }
}
