#include <bits/stdc++.h>
using namespace std;
const int inf = (-1ull >> 1);
const int N = 81;
long long a1[N + 1], an[N + 1], b1[N + 1], bn[N + 1];
long long f[N + 1], g[N + 1];
void init(int n) {
  f[0] = 1;
  f[1] = 2;
  g[1] = 1;
  for (int i = 2; i <= n; i++) {
    f[i] = f[i - 1] + f[i - 2];
    g[i] = g[i - 2] + 1;
  }
}
void doit(int n, long long d1[], long long dn[], long long x) {
  if (n == 0) {
    a1[n] = 0, an[n] = 0;
    return;
  }
  if (n == 1) {
    d1[n] = x == 1 ? 0 : 1;
    dn[n] = x == 1 ? 1 : 0;
    return;
  }
  if (x <= f[n - 1]) {
    doit(n - 1, d1, dn, x);
    d1[n] = min(d1[n - 1], dn[n - 1] + 2);
    dn[n] = min(d1[n - 1], dn[n - 1]) + 1 + g[n - 2];
    return;
  } else if (x > f[n - 1]) {
    doit(n - 2, d1, dn, x - f[n - 1]);
    d1[n] = d1[n - 2] + 1;
    dn[n] = dn[n - 2];
    return;
  }
}
long long solve(int n, long long x, long long y) {
  if (n == 0) return 0;
  if (n == 1) return 1;
  int res = 0;
  long long nu;
  if (x <= f[n - 1] && y > f[n - 1]) {
    nu = min(a1[n - 1], an[n - 1]);
    res = nu + 1 + b1[n - 2];
  } else if (x <= f[n - 1] && y <= f[n - 1]) {
    nu = solve(n - 1, x, y);
    res = min(nu, min(a1[n - 1] + bn[n - 1], an[n - 1] + b1[n - 1]) + 2);
  } else {
    res = solve(n - 2, x - f[n - 1], y - f[n - 1]);
  }
  return res;
}
int main() {
  init(N);
  int t;
  long long a, b;
  int n;
  scanf("%d %d", &t, &n);
  if (n >= N) n = N;
  while (t--) {
    scanf("%I64d %I64d", &a, &b);
    if (a > b) swap(a, b);
    doit(n, a1, an, a);
    doit(n, b1, bn, b);
    printf("%I64d\n", solve(n, a, b));
  }
  return 0;
}
