#include <bits/stdc++.h>
using namespace std;
int N, M;
long long S[110], D[110];
long long dw[2][110], tp[2][110];
void eval(int k, long long x, long long* d, long long* t) {
  if (k == 0) return;
  if (k == 1) {
    if (x == 1LL)
      d[k] = 0LL, t[k] = 1LL;
    else if (x == 2LL)
      d[k] = 1LL, t[k] = 0LL;
    return;
  }
  if (x <= S[k - 1]) {
    eval(k - 1, x, d, t);
    d[k] = min(d[k - 1], t[k - 1] + 2LL);
    t[k] = min(t[k - 1], d[k - 1]) + D[k - 2] + 1LL;
  } else if (x > S[k - 1]) {
    eval(k - 2, x - S[k - 1], d, t);
    d[k] = d[k - 2] + 1LL;
    t[k] = t[k - 2];
  }
}
long long solve(int k, long long st, long long en, int mm) {
  if (st == en || k == 0) return 0LL;
  if (en == st + 1 || k == 1) return 1LL;
  if (st == 1 && en == S[k]) return D[k];
  if (mm != -1 && st == 1) return dw[mm][k];
  if (mm != -1 && en == S[k]) return tp[mm][k];
  long long xx = S[k - 1], res, r, r1, r2;
  if (st <= xx && en <= xx) {
    r1 = min(solve(k - 1, 1, st, 0), solve(k - 1, st, xx, 0));
    r2 = min(solve(k - 1, 1, en, 1), solve(k - 1, en, xx, 1));
    r = solve(k - 1, st, en, -1);
    res = min(r, r1 + r2 + 2LL);
  } else if (st <= xx && en > xx) {
    r1 = solve(k - 1, 1, st, 0);
    r2 = solve(k - 1, st, xx, 0);
    r = solve(k - 2, 1, en - xx, 1);
    res = r + min(r1, r2) + 1LL;
  } else if (st > xx && en > xx)
    res = solve(k - 2, st - xx, en - xx, -1);
  return res;
}
vector<pair<long long, long long> > Q;
long long ans;
int main() {
  scanf("%d%d", &M, &N);
  long long x, y, mi, mx, ans, ff, tot;
  ff = 0LL;
  for (int i = 0; i < M; i++) {
    scanf("%I64d%I64d", &x, &y);
    mi = min(x, y);
    mx = max(x, y);
    ff = max(ff, mx);
    Q.push_back(make_pair(mi, mx));
  }
  S[0] = 1LL, S[1] = 2LL, D[0] = 0LL, D[1] = 1LL;
  tot = min(N, 80);
  for (int i = 2; i <= tot; i++) {
    S[i] = S[i - 1] + S[i - 2];
    D[i] = D[i - 2] + 1LL;
  }
  for (int i = 0; i < M; i++) {
    mi = Q[i].first, mx = Q[i].second;
    for (int j = 0; j <= tot; j++)
      dw[0][j] = dw[1][j] = tp[0][j] = tp[1][j] = 0LL;
    eval(tot, mi, dw[0], tp[0]);
    eval(tot, mx, dw[1], tp[1]);
    ans = solve(tot, mi, mx, -1);
    printf("%I64d\n", ans);
  }
  return 0;
}
