#include <bits/stdc++.h>
using namespace std;
template <typename T>
void chkmax(T &x, T y) {
  x = x > y ? x : y;
}
template <typename T>
void chkmin(T &x, T y) {
  x = x > y ? y : x;
}
const long long INF = (1ll << 62) - 1;
template <typename T>
void read(T &x) {
  x = 0;
  bool f = 1;
  char ch;
  do {
    ch = getchar();
    if (ch == '-') f = 0;
  } while (ch > '9' || ch < '0');
  do {
    x = x * 10 + ch - '0';
    ch = getchar();
  } while (ch >= '0' && ch <= '9');
  x = f ? x : -x;
}
template <typename T>
void write(T x) {
  if (x < 0) x = ~x + 1, putchar('-');
  if (x > 9) write(x / 10);
  putchar(x % 10 + '0');
}
const int M = 80 + 5;
const int N = 222 + 7;
pair<long long, int> head[M][N], tail[M][N];
int n, q, hn[N], tn[N];
long long f[M];
inline int work(long long a, long long b, int n) {
  if (a > b) swap(a, b);
  if (a == b) return 0;
  if (n == 2 || n == 1 || a + 1 == b) return 1;
  if (a == 1) {
    for (int i = 0; i < hn[n]; i++) {
      if (head[n][i].first == b) return head[n][i].second;
    }
  }
  if (b == f[n + 1]) {
    for (int i = 0; i < tn[n]; i++) {
      if (tail[n][i].first == a) return tail[n][i].second;
    }
  }
  int ans = 0;
  if (a <= f[n] && b <= f[n])
    ans = min(work(a, b, n - 1),
              min(work(1, a, n - 1) + work(b, f[n], n - 1) + 2,
                  work(1, b, n - 1) + work(a, f[n], n - 1) + 2));
  else if (a <= f[n] && b > f[n])
    ans = min(work(a, 1, n - 1), work(a, f[n], n - 1)) +
          work(b - f[n], 1, n - 2) + 1;
  else if (a > f[n] && b > f[n])
    ans = work(a - f[n], b - f[n], n - 2);
  if (a == 1) head[n][hn[n]++] = make_pair(b, ans);
  if (b == f[n + 1]) tail[n][tn[n]++] = make_pair(a, ans);
  return ans;
}
signed main() {
  read(q);
  read(n);
  f[1] = 1;
  f[2] = 2;
  int x = 3;
  while (1) {
    f[x] = f[x - 1] + f[x - 2];
    if (f[x] > 1e16) break;
    x++;
  }
  n = min(n, x - 1);
  for (int i = 1; i <= q; i++) {
    long long a, b;
    read(a);
    read(b);
    if (a > b) swap(a, b);
    int pos = lower_bound(f + 1, f + x + 1, b) - f + 1;
    int m = min(n, pos);
    for (int j = 1; j <= n; j++) hn[j] = tn[j] = 0;
    printf("%d\n", work(a, b, m));
  }
  return 0;
}
