#include <bits/stdc++.h>
using namespace std;
const int N = 100;
long long D[N];
int dia[N];
int dp[N][4];
long long num[N][2];
int f(long long a, long long b, int n) {
  if (a > b) swap(a, b);
  if (a == b) return 0;
  if (b < 4) return 1;
  if (a == 1 and b == D[n]) return dia[n];
  int typ = 4;
  if (a == 1 and b == num[n][0])
    typ = 0;
  else if (a == 1 and b == num[n][1])
    typ = 1;
  else if (a == num[n][0] and b == D[n])
    typ = 2;
  else if (a == num[n][1] and b == D[n])
    typ = 3;
  if (typ != 4 and dp[n][typ] != -1) return dp[n][typ];
  int res;
  if (a <= D[n - 1] and b > D[n - 1])
    res = min(f(1, a, n - 1), f(a, D[n - 1], n - 1)) + 1 +
          f(1, b - D[n - 1], n - 2);
  else if (a > D[n - 1])
    res = f(a - D[n - 1], b - D[n - 1], n - 2);
  else
    res =
        min(f(a, b, n - 1), min(f(1, a, n - 1), f(a, D[n - 1], n - 1)) +
                                min(f(b, D[n - 1], n - 1), f(1, b, n - 1)) + 2);
  if (typ != 4) dp[n][typ] = res;
  return res;
}
signed main() {
  D[1] = 2;
  D[2] = 3;
  for (int i = 3; i < 81; i++) D[i] = D[i - 1] + D[i - 2];
  int t, n;
  scanf("%d %d", &t, &n);
  n = min(n, 80);
  dia[0] = 0;
  dia[1] = 1;
  dia[2] = 1;
  for (int i = 3; i <= n; i++) dia[i] = 1 + dia[i - 2];
  while (t--) {
    long long a, b;
    scanf("%lld %lld", &a, &b);
    if (a > b) swap(a, b);
    long long q = a;
    long long p = b;
    for (int i = n; i > 0; i--) {
      if (q > D[i]) q -= D[i];
      if (p > D[i]) p -= D[i];
      num[i][0] = q;
      num[i][1] = p;
      dp[i][0] = dp[i][1] = dp[i][2] = dp[i][3] = -1;
    }
    printf("%d\n", f(a, b, n));
  }
  return 0;
}
