#include <bits/stdc++.h>
using namespace std;
vector<long long> graph_size, a_to_first, a_to_last, b_to_first, b_to_last;
const long long MAXIMUM = 10000000000000000;
void Init(long long x, int n, vector<long long> &first,
          vector<long long> &last) {
  if (n == 0) {
    first[0] = 0;
    last[0] = 0;
    return;
  }
  if (n == 1) {
    if (x == 2)
      first[1] = 1;
    else
      first[1] = 0;
    if (x == 1)
      last[1] = 1;
    else
      last[1] = 0;
    return;
  }
  if (x <= graph_size[n - 1]) {
    Init(x, n - 1, first, last);
    first[n] = min(first[n - 1], last[n - 1] + 2);
    last[n] = min(first[n - 1], last[n - 1]) + 1 + (n - 2 + 1) / 2;
  } else {
    Init(x - graph_size[n - 1], n - 2, first, last);
    first[n] = first[n - 2] + 1;
    last[n] = last[n - 2];
  }
}
long long dist(long long a, long long b, int n) {
  if (a == b) return 0;
  if (n <= 2) return 1;
  if (a <= graph_size[n - 1]) {
    if (b >= graph_size[n - 1] + 1) {
      return min(a_to_first[n - 1], a_to_last[n - 1]) + b_to_first[n - 2] + 1;
    } else {
      return min(dist(a, b, n - 1),
                 min(a_to_first[n - 1] + 2 + b_to_last[n - 1],
                     a_to_last[n - 1] + 2 + b_to_first[n - 1]));
    }
  } else {
    return dist(a - graph_size[n - 1], b - graph_size[n - 1], n - 2);
  }
}
int main() {
  int t, n;
  cin >> t >> n;
  graph_size.push_back(1);
  graph_size.push_back(2);
  int iMax = 2;
  for (; graph_size.back() < MAXIMUM; ++iMax) {
    graph_size.push_back(graph_size[iMax - 1] + graph_size[iMax - 2]);
  }
  for (int i = 1; i <= t; ++i) {
    long long a, b;
    cin >> a >> b;
    if (a > b) swap(a, b);
    int k = min(n, iMax);
    a_to_first.resize(k + 1, 0);
    a_to_last.resize(k + 1, 0);
    b_to_first.resize(k + 1, 0);
    b_to_last.resize(k + 1, 0);
    Init(a, k, a_to_first, a_to_last);
    Init(b, k, b_to_first, b_to_last);
    cout << dist(a, b, k) << endl;
  }
  return 0;
}
