#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000 + 5;
const long long MAX = 1e16;
long long D[MAXN], num[MAXN][2];
int dp[MAXN][5];
int calc(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 type = -1;
  int ans = 0;
  if (a == 1 && b == D[n])
    type = 0;
  else if (a == 1 && b == num[n][0])
    type = 1;
  else if (a == 1 && b == num[n][1])
    type = 2;
  else if (b == D[n] && a == num[n][0])
    type = 3;
  else if (b == D[n] && a == num[n][1])
    type = 4;
  if (type != -1 && dp[n][type] != -1) return dp[n][type];
  if (a <= D[n - 1] && b >= D[n - 1] + 1)
    ans = min(calc(1, a, n - 1), calc(a, D[n - 1], n - 1)) +
          calc(1, b - D[n - 1], n - 2) + 1;
  else if (a >= D[n - 1] + 1 && b >= D[n - 1] + 1)
    ans = calc(a - D[n - 1], b - D[n - 1], n - 2);
  else {
    int tmp1 = calc(a, b, n - 1);
    int tmp2 = min(calc(1, a, n - 1), calc(a, D[n - 1], n - 1));
    int tmp3 = min(calc(1, b, n - 1), calc(b, D[n - 1], n - 1));
    ans = min(tmp1, tmp2 + tmp3 + 2);
  }
  if (type != -1) dp[n][type] = ans;
  return ans;
}
int main() {
  int t, n;
  scanf("%d%d", &t, &n);
  D[0] = 1, D[1] = 2;
  int pos = 2;
  while (true) {
    D[pos] = D[pos - 1] + D[pos - 2];
    if (D[pos] > MAX) break;
    pos++;
  }
  n = min(n, pos);
  for (int i = 0; i < t; i++) {
    long long a, b;
    scanf("%I64d%I64d", &a, &b);
    if (a > b) swap(a, b);
    long long q1 = a, q2 = b;
    for (int j = n; j >= 0; j--) {
      if (q1 > D[j]) q1 -= D[j];
      if (q2 > D[j]) q2 -= D[j];
      num[j][0] = q1;
      num[j][1] = q2;
      dp[j][0] = dp[j][1] = dp[j][2] = dp[j][3] = dp[j][4] = -1;
    }
    printf("%d\n", calc(a, b, n));
  }
  return 0;
}
