#include <bits/stdc++.h>
using namespace std;
long long f[105];
void calc(long long a, int n, long long *a1, long long *a2) {
  if (n <= 1) return (void)(a1[n] = (a != 1), a2[n] = (a != f[n]));
  if (a > f[n - 1])
    return (void)(calc(a - f[n - 1], n - 2, a1, a2), a1[n] = a1[n - 2] + 1,
                  a2[n] = a2[n - 2]);
  calc(a, n - 1, a1, a2);
  a1[n] = min(a1[n - 1], a2[n - 1] + 2);
  a2[n] = min(a1[n - 1], a2[n - 1]) + 1 + (n - 1) / 2;
  return;
}
long long a1[105], a2[105], b1[105], b2[105];
long long solve(long long a, long long b, int n) {
  if (n <= 1) return a != b;
  if (a > f[n - 1] && b > f[n - 1])
    return solve(a - f[n - 1], b - f[n - 1], n - 2);
  if (a <= f[n - 1] && b > f[n - 1])
    return min(a1[n - 1], a2[n - 1]) + 1 + b1[n - 2];
  return min(solve(a, b, n - 1),
             min(a1[n - 1] + b2[n - 1], a2[n - 1] + b1[n - 1]) + 2);
}
signed main() {
  ios::sync_with_stdio(false);
  int T, n;
  cin >> T >> n;
  n = min(n, 79);
  f[0] = 1, f[1] = 2;
  for (int i = 2; i <= n; ++i) f[i] = f[i - 1] + f[i - 2];
  while (T--) {
    long long a, b;
    cin >> a >> b;
    if (a > b) swap(a, b);
    calc(a, n, a1, a2), calc(b, n, b1, b2);
    cout << solve(a, b, n) << "\n";
  }
}
