#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000000;
const int prime = 9241;
const long double pi = acos(-1.);
long long fibs[150];
int d[150];
int fcnt;
int it = 0;
pair<long long, pair<int, int> > cash[155][5];
int cnt[155];
pair<int, int> tofl(long long v, int num) {
  for (int i = 0; i < cnt[num]; i++)
    if (cash[num][i].first == v) return cash[num][i].second;
  if (num == 0) return make_pair(0, 0);
  if (num == 1) return make_pair(v == 1LL ? 0 : 1, v == 1LL ? 1 : 0);
  if (v > fibs[num - 1]) {
    pair<int, int> t = tofl(v - fibs[num - 1], num - 2);
    pair<int, int> ans = make_pair(t.first + 1, t.second);
    cash[num][cnt[num]++] = make_pair(v, ans);
    return ans;
  }
  pair<int, int> t = tofl(v, num - 1);
  pair<int, int> ans = make_pair(min(t.first, t.second + 2),
                                 min(t.first, t.second) + 1 + d[num - 2]);
  cash[num][cnt[num]++] = make_pair(v, ans);
  return ans;
}
int tofirst(long long v, int num) { return tofl(v, num).first; }
int tolast(long long v, int num) { return tofl(v, num).second; }
int between(long long a, long long b, int num) {
  if (a == b) return 0;
  if (fabs(a - b) == 1ll) return 1;
  if (a < b) swap(a, b);
  if (b > fibs[num - 1])
    return between(a - fibs[num - 1], b - fibs[num - 1], num - 2);
  pair<int, int> toa, tob;
  if (a <= fibs[num - 1]) {
    toa = tofl(a, num - 1);
    tob = tofl(b, num - 1);
    return min(min(toa.first, toa.second) + min(tob.first, tob.second) + 2,
               between(a, b, num - 1));
  }
  tob = tofl(b, num - 1);
  return min(tob.first, tob.second) + 1 + tofirst(a - fibs[num - 1], num - 2);
}
int go_between(long long a, long long b, int num) {
  for (int i = 0; i <= num; i++) cnt[i] = 0;
  return between(a, b, num);
}
int main() {
  fibs[0] = 1ll, fibs[1] = 2ll;
  d[0] = 0;
  d[1] = 1;
  for (int i = 2;; i++) {
    d[i] = d[i - 2] + 1;
    fibs[i] = fibs[i - 1] + fibs[i - 2];
    if (fibs[i] > 1e18) {
      fcnt = i;
      break;
    }
  }
  int q, n;
  cin >> q >> n;
  for (int i = 0; i < q; i++) {
    long long a, b;
    cin >> a >> b;
    it = 0;
    cout << go_between(a, b, min(n, fcnt - 1)) << endl;
  }
  cerr << (double)clock() / (double)CLOCKS_PER_SEC << endl;
}
