#include <bits/stdc++.h>
using namespace std;
const long long mod = 1000000007;
long long Fib[100];
long long Path[100];
pair<long long, long long> get(long long N, long long X, bool f) {
  assert(Fib[N] >= X);
  if (N <= 0) {
    return {0, 0};
  }
  if (N == 1) {
    if (X == 1) {
      return {0, 1};
    } else {
      return {1, 0};
    }
  }
  pair<long long, long long> res = {};
  if (X <= Fib[N - 1]) {
    res = get(N - 1, X, true);
    res.second = min(res.first, res.second) + 1ll + Path[N - 2];
    if (f) {
      res.second = min(res.second, res.first + 2ll);
      res.first = min(res.first, res.second + 2ll);
    }
  } else {
    res = get(N - 2, X - Fib[N - 1], false);
    res.first++;
    if (f) {
      res.second = min(res.second, res.first + 2ll);
      res.first = min(res.first, res.second + 2ll);
    }
  }
  return res;
}
long long solve(long long N, long long X, long long Y) {
  int f = 0;
  if (N > 90) {
    N = 90;
    f = 1;
  }
  assert(Fib[N] >= X && Fib[N] >= Y);
  if (X > Y) swap(X, Y);
  while (true) {
    if (Y <= Fib[N - 1]) {
      f = 1;
      N--;
    } else if (X > Fib[N - 1]) {
      if (f) {
        f++;
      }
      X -= Fib[N - 1];
      Y -= Fib[N - 1];
      N -= 2;
    } else {
      break;
    }
  }
  if (N == 1) {
    return 1;
  }
  auto res1 = get(N - 1, X, true);
  auto res2 = get(N - 2, Y - Fib[N - 1], false);
  long long res = res2.first + 1ll + min(res1.first, res1.second);
  if (f) {
    res = min(res, res2.second + 2ll + res1.first + f - 1ll);
  }
  return res;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  Fib[0] = 1;
  Path[0] = 0;
  Fib[1] = 2;
  Path[1] = 1;
  for (int i = 2; i < 100; i++) {
    Fib[i] = Fib[i - 1] + Fib[i - 2];
    Path[i] = Path[i - 2] + 1;
  }
  long long T, N, X, Y;
  cin >> T >> N;
  while (T--) {
    cin >> X >> Y;
    cout << solve(N, X, Y) << '\n';
  }
  return 0;
}
