#include <bits/stdc++.h>
using namespace std;
long long fib_num[1000];
int solutions[1010][5];
long long key[1010][2];
inline int request(long long a, long long b, int n) {
  if (a > b) swap(a, b);
  if (a == b) return 0;
  if (n == 1 || n == 2) return 1;
  int idx = -1;
  long long V = fib_num[n], u = fib_num[n - 1];
  if (a == 1) {
    if (b == V)
      idx = 0;
    else if (b == key[n][0])
      idx = 1;
    else if (b == key[n][1])
      idx = 2;
  } else if (b == V) {
    if (a == key[n][0])
      idx = 3;
    else if (a == key[n][1])
      idx = 4;
  }
  if (idx != -1 && solutions[n][idx] != -1) return solutions[n][idx];
  if (a > u && b > u) {
    long long ans = request(a - u, b - u, n - 2);
    solutions[n][idx] = ans;
    return ans;
  }
  if (a <= u && b <= u) {
    long long a1, b1, c1;
    a1 = request(a, b, n - 1);
    b1 = request(1, a, n - 1) + request(b, u, n - 1) + 2;
    c1 = request(1, b, n - 1) + request(a, u, n - 1) + 2;
    long long ans = min(a1, min(b1, c1));
    solutions[n][idx] = ans;
    return ans;
  }
  long long a1 = request(1, b - u, n - 2);
  long long b1 = min(request(1, a, n - 1), request(a, u, n - 1));
  solutions[n][idx] = a1 + b1 + 1;
  return a1 + b1 + 1;
}
int main() {
  int t, n;
  scanf("%d%d", &t, &n);
  fib_num[0] = 1;
  fib_num[1] = 2;
  int num = 1;
  while (fib_num[num] < (long long)2 * 1e+16) {
    fib_num[num + 1] = fib_num[num] + fib_num[num - 1];
    ++num;
  }
  n = min(n, num);
  for (int i = 0; i < t; ++i) {
    long long a, b, aa, bb;
    cin >> a >> b;
    if (a > b) swap(a, b);
    long long j;
    for (aa = a, bb = b, j = n; j >= 0; --j) {
      if (aa > fib_num[j]) aa -= fib_num[j];
      if (bb > fib_num[j]) bb -= fib_num[j];
      key[j][0] = aa;
      key[j][1] = bb;
      for (int k = 0; k <= 4; ++k) solutions[j][k] = -1;
    }
    printf("%d\n", request(a, b, n));
  }
  return 0;
}
