#include <bits/stdc++.h>
using namespace std;
long long p[105][4], g[105][4][4], f[105];
inline long long min(long long a, long long b) { return a < b ? a : b; }
long long ask(int a, int b, int n) {
  if (n < 0 || p[n][a] == p[n][b]) return 0;
  if (g[n][a][b]) return g[n][a][b];
  if (p[n][a] > f[n - 1] && p[n][b] > f[n - 1])
    return g[n][a][b] = ask(a, b, n - 2);
  if (p[n][b] > f[n - 1])
    return g[n][a][b] =
               min(ask(0, a, n - 1), ask(a, 3, n - 1)) + ask(0, b, n - 2) + 1;
  ask(a, b, n - 1);
  return g[n][a][b] =
             min(ask(a, b, n - 1), min(ask(0, a, n - 1) + ask(b, 3, n - 1),
                                       ask(a, 3, n - 1) + ask(0, b, n - 1)) +
                                       2);
}
int main() {
  int t, n;
  cin >> t >> n;
  n = min(n, 77);
  f[0] = 1, f[1] = 2, g[1][0][3] = 1;
  p[0][0] = p[0][3] = p[1][0] = 1, p[1][3] = 2;
  for (int i = 2; i <= n; ++i)
    p[i][3] = f[i] = f[i - 1] + f[i - 2], p[i][0] = 1;
  long long a, b;
  for (int i = 1; i <= t; ++i) {
    scanf("%I64d%I64d", &a, &b);
    if (a > b) swap(a, b);
    for (int j = n; j; --j) {
      p[j][1] = a, p[j][2] = b;
      if (a > f[j - 1]) a -= f[j - 1];
      if (b > f[j - 1]) b -= f[j - 1];
      for (int k = 0; k < 4; ++k)
        for (int d = 0; d < 4; ++d) g[j][k][d] = 0;
      g[j][0][3] = (j + 1) / 2;
    }
    p[0][1] = a, p[0][2] = b;
    printf("%I64d\n", ask(1, 2, n));
  }
  return 0;
}
