#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
template <typename T>
inline void setmin(T& x, T y) {
  if (y < x) x = y;
}
template <typename T>
inline void setmax(T& x, T y) {
  if (y > x) x = y;
}
template <class T1, class T2, class T3>
struct triple {
  T1 a;
  T2 b;
  T3 c;
  triple() : a(T1()), b(T2()), c(T3()){};
  triple(T1 _a, T2 _b, T3 _c) : a(_a), b(_b), c(_c) {}
};
template <class T1, class T2, class T3>
bool operator<(const triple<T1, T2, T3>& t1, const triple<T1, T2, T3>& t2) {
  if (t1.a != t2.a)
    return t1.a < t2.a;
  else if (t1.b != t2.b)
    return t1.b < t2.b;
  else
    return t1.c < t2.c;
}
template <class T1, class T2, class T3>
bool operator>(const triple<T1, T2, T3>& t1, const triple<T1, T2, T3>& t2) {
  if (t1.a != t2.a)
    return t1.a > t2.a;
  else if (t1.b != t2.b)
    return t1.b > t2.b;
  else
    return t1.c > t2.c;
}
template <class T1, class T2, class T3>
bool operator==(const triple<T1, T2, T3>& t1, const triple<T1, T2, T3>& t2) {
  return (t1.a == t2.a && t1.b == t2.b && t1.c == t2.c);
}
template <class T1, class T2, class T3>
inline istream& operator>>(istream& os, triple<T1, T2, T3>& t) {
  return os >> t.a >> t.b >> t.c;
}
template <class T1, class T2, class T3>
ostream& operator<<(ostream& os, const triple<T1, T2, T3>& t) {
  return os << t.a << " " << t.b << " " << t.c;
}
template <class T1, class T2>
inline pair<T1, T2> operator+(const pair<T1, T2>& p1, const pair<T1, T2>& p2) {
  return pair<T1, T2>(p1.first + p2.first, p1.second + p2.second);
}
template <class T1, class T2>
inline pair<T1, T2>& operator+=(pair<T1, T2>& p1, const pair<T1, T2>& p2) {
  p1.first += p2.first, p1.second += p2.second;
  return p1;
}
template <class T1, class T2>
inline pair<T1, T2> operator-(const pair<T1, T2>& p1, const pair<T1, T2>& p2) {
  return pair<T1, T2>(p1.first - p2.first, p1.second - p2.second);
}
template <class T1, class T2>
inline pair<T1, T2>& operator-=(pair<T1, T2>& p1, const pair<T1, T2>& p2) {
  p1.first -= p2.first, p1.second -= p2.second;
  return p1;
}
template <class T1, class T2>
inline istream& operator>>(istream& os, pair<T1, T2>& p) {
  return os >> p.first >> p.second;
}
template <class T1, class T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
  return os << p.first << " " << p.second;
}
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const long long LL_INF = 0x3f3f3f3f3f3f3f3f;
const ld PI = acos(-1);
const int N = 1e3 + 7;
long long D[N];
pair<long long, int> MEM[90][200][2];
int id[90][20];
long long dist(long long a, long long b, int n) {
  if (a == b) return 0;
  if (abs(a - b) == 1) return 1;
  if (a > b) swap(a, b);
  if (a == 1) {
    for (int i = 0; i <= id[n][0] - 1; i++) {
      if (MEM[n][i][0].first == b) return MEM[n][i][0].second;
    }
  }
  if (b == D[n]) {
    for (int i = 0; i <= id[n][1] - 1; i++) {
      if (MEM[n][i][1].first == a) return MEM[n][i][1].second;
    }
  }
  long long temp;
  if (a >= D[n - 1] + 1 and b >= D[n - 1] + 1) {
    temp = dist(a - D[n - 1], b - D[n - 1], n - 2);
  } else if (a <= D[n - 1] and b >= D[n - 1] + 1) {
    long long A = min(dist(a, D[n - 1], n - 1), dist(1, a, n - 1)) + 1;
    temp = A + dist(1, b - D[n - 1], n - 2);
  } else {
    long long A = min(dist(1, a, n - 1), dist(a, D[n - 1], n - 1)) + 1;
    long long B = min(dist(1, b, n - 1), dist(b, D[n - 1], n - 1)) + 1;
    temp = min(A + B, dist(a, b, n - 1));
  }
  if (a == 1) MEM[n][id[n][0]++][0] = {b, temp};
  if (b == D[n]) MEM[n][id[n][1]++][1] = {a, temp};
  return temp;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  int nMax;
  D[0] = 1, D[1] = 2;
  for (int i = 2;; i++) {
    D[i] = D[i - 1] + D[i - 2];
    if (D[i] > 1e18) {
      nMax = i;
      break;
    }
  }
  int t, n;
  cin >> t >> n;
  while (t--) {
    long long a, b;
    cin >> a >> b;
    if (a > b) swap(a, b);
    for (int i = 0; i <= min(n, nMax); i++) id[i][0] = id[i][1] = 0;
    int m = min(n, int(lower_bound(D, D + nMax, b) - D + 1));
    cout << dist(a, b, m) << "\n";
  }
  exit(0);
}
