#include <bits/stdc++.h>
using namespace std;
const double eps(1e-8);
int t, n;
long long f[110];
long long key[81][2];
int have[81][6];
int flag[81][6];
char s1[20], s2[20], p[20];
char s[100];
int ca;
int cal(int n, long long a, long long b) {
  if (a == 1 && b == f[n]) return 4;
  if (a == 1)
    return (b == key[n][1]);
  else if (b == f[n])
    return (a == key[n][1]) + 2;
  else
    return 5;
}
int solve(int n, long long a, long long b) {
  if (a == b) return 0;
  if (n == 1 || n == 2) return 1;
  if (a > b) swap(a, b);
  if (a == 1 && b == f[n]) return (n + 1) / 2;
  int ty = cal(n, a, b);
  if (flag[n][ty] == ca) return have[n][ty];
  flag[n][ty] = ca;
  if (a <= f[n - 1] && b > f[n - 1])
    return have[n][ty] = min(solve(n - 1, 1, a), solve(n - 1, a, f[n - 1])) +
                         solve(n - 2, 1, b - f[n - 1]) + 1;
  else if (a > f[n - 1] && b > f[n - 1])
    return have[n][ty] = solve(n - 2, a - f[n - 1], b - f[n - 1]);
  else
    return have[n][ty] =
               min(solve(n - 1, a, b),
                   min(solve(n - 1, 1, a) + solve(n - 1, b, f[n - 1]),
                       solve(n - 1, 1, b) + solve(n - 1, a, f[n - 1])) +
                       2);
}
int main() {
  f[1] = 2;
  f[2] = 3;
  for (int i = (3); i <= (100); ++i) f[i] = f[i - 1] + f[i - 2];
  scanf("%d %d\n", &t, &n);
  n = min(n, 80);
  ca = 0;
  for (int i = (1); i <= (t); ++i) {
    ca++;
    long long a = 0, b = 0;
    gets(s);
    int l = strlen(s);
    int j;
    for (j = 0; s[j] != ' '; j++) a = a * 10 + s[j] - '0';
    j++;
    for (; j < l; j++) b = b * 10 + s[j] - '0';
    if (a > b) swap(a, b);
    long long ta = a, tb = b;
    for (int j = (n); j >= (1); --j) {
      if (ta > f[j]) ta -= f[j];
      if (tb > f[j]) tb -= f[j];
      key[j][0] = ta;
      key[j][1] = tb;
    }
    long long ans = solve(n, a, b);
    memset(p, 0, sizeof(p));
    int top = -1;
    while (ans) {
      p[++top] = ans % 10 + '0';
      ans /= 10;
    }
    l = strlen(p);
    reverse(p, p + l);
    puts(p);
  }
}
