#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
const long long inf = (long long)1e16 + 1;
struct _two {
  int a, b;
  inline void Input(int A, int B) {
    a = A;
    b = B;
  }
};
long long len[N];
long long ans;
bool flag;
int n, t;
void Init() {
  scanf("%d%d", &t, &n);
  len[0] = 1;
  len[1] = 2;
  for (int i = 2; i <= n; i++) {
    len[i] = len[i - 1] + len[i - 2];
    if (len[i] > inf) len[i] = inf;
  }
}
_two dfs(int x, long long a, long long b) {
  _two temp;
  if (x <= 1) {
    temp.Input(a - 1, x + 1 - a);
    if (b != -1) {
      temp.b = 0;
      ans = ((ans) < (1) ? (ans) : (1));
      flag = 1;
    }
    return temp;
  }
  if (b == -1) {
    if (a > len[x - 1]) {
      temp = dfs(x - 2, a - len[x - 1], -1);
      temp.a++;
    } else {
      _two temp1;
      temp1 = dfs(x - 1, a, -1);
      temp.b =
          ((temp1.a) < (temp1.b) ? (temp1.a) : (temp1.b)) + 1 + (x - 1) / 2;
      temp.a = ((temp1.a) < (temp1.b + 2) ? (temp1.a) : (temp1.b + 2));
    }
    return temp;
  } else {
    if (a <= len[x - 1] && b > len[x - 1]) {
      _two temp1, temp2;
      temp1 = dfs(x - 1, a, -1);
      temp2 = dfs(x - 2, b - len[x - 1], -1);
      if (flag) {
        temp.Input(0, 0);
        return temp;
      }
      ans = ((ans) < (((temp1.a) < (temp1.b) ? (temp1.a) : (temp1.b)) +
                      temp2.a + 1)
                 ? (ans)
                 : (((temp1.a) < (temp1.b) ? (temp1.a) : (temp1.b)) + temp2.a +
                    1));
      temp.b = temp2.b;
      temp.a = ((temp1.a) < (temp1.b + 2) ? (temp1.a) : (temp1.b + 2));
      return temp;
    } else {
      if (a > len[x - 1]) {
        temp = dfs(x - 2, a - len[x - 1], b - len[x - 1]);
        temp.a++;
        return temp;
      } else {
        temp = dfs(x - 1, a, b);
        if (!flag)
          ans = ((ans) < (temp.a + temp.b + 2) ? (ans) : (temp.a + temp.b + 2));
        flag = 1;
        temp.Input(0, 0);
        return temp;
      }
    }
  }
}
void Work() {
  long long x, y;
  while (t--) {
    scanf("%I64d%I64d", &x, &y);
    if (x > y) {
      long long temp = x;
      x = y;
      y = temp;
    }
    if (x == y)
      puts("0");
    else {
      ans = inf;
      flag = 0;
      dfs(n, x, y);
      printf("%I64d\n", ans);
    }
  }
}
int main() {
  Init();
  Work();
  return 0;
}
