#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e16;
long long f[110] = {1, 2};
long long g[110][5][5], p[110][5];
int n, m;
struct ios {
  inline char read() {
    static const int IN_LEN = 1 << 18 | 1;
    static char buf[IN_LEN], *s, *t;
    return (s == t) && (t = (s = buf) + fread(buf, 1, IN_LEN, stdin)),
           s == t ? -1 : *s++;
  }
  template <typename _Tp>
  inline ios& operator>>(_Tp& x) {
    static char c11, boo;
    for (c11 = read(), boo = 0; !isdigit(c11); c11 = read()) {
      if (c11 == -1) return *this;
      boo |= c11 == '-';
    }
    for (x = 0; isdigit(c11); c11 = read()) x = x * 10 + (c11 ^ '0');
    boo && (x = -x);
    return *this;
  }
} io;
long long _min(long long a, long long b) { return a < b ? a : b; }
long long work(int la, int lb, int lc) {
  if (lc < 0) return 0;
  if (g[lc][la][lb] != inf) return g[lc][la][lb];
  long long ans = inf;
  if (p[lc][la] > f[lc - 1] && p[lc][lb] > f[lc - 1])
    ans = work(la, lb, lc - 2);
  else if (p[lc][lb] > f[lc - 1])
    ans = work(0, lb, lc - 2) + _min(work(0, la, lc - 1), work(la, 3, lc - 1)) +
          1;
  else
    ans = _min(work(la, lb, lc - 1),
               _min(work(0, la, lc - 1) + work(lb, 3, lc - 1),
                    work(0, lb, lc - 1) + work(la, 3, lc - 1)) +
                   2);
  return g[lc][la][lb] = ans;
}
int main() {
  int i, j, li, lj;
  io >> m >> n;
  for (i = 2; f[i - 1] <= 1e16; i++) f[i] = f[i - 1] + f[i - 2];
  n = _min(i - 1, n);
  while (m--) {
    long long la, lb;
    io >> la >> lb;
    if (la > lb) swap(la, lb);
    for (i = n; i >= 0; --i) {
      p[i][0] = 1, p[i][3] = f[i], p[i][1] = la, p[i][2] = lb;
      if (i && la > f[i - 1]) la -= f[i - 1];
      if (i && lb > f[i - 1]) lb -= f[i - 1];
      for (j = 0; j <= 3; j++)
        for (li = 0; li <= 3; li++)
          if (j != li) g[i][j][li] = inf;
      g[j][0][3] = (j + 1) / 2;
    }
    printf("%lld\n", work(1, 2, n));
  }
  return 0;
}
