233_E. Doe Graphs_10260
John Doe decided that some mathematical object must be named after him. So he invented the Doe graphs. The Doe graphs are a family of undirected graphs, each of them is characterized by a single non-negative number — its order. 

We'll denote a graph of order k as D(k), and we'll denote the number of vertices in the graph D(k) as |D(k)|. Then let's define the Doe graphs as follows:

  * D(0) consists of a single vertex, that has number 1. 
  * D(1) consists of two vertices with numbers 1 and 2, connected by an edge. 
  * D(n) for n ≥ 2 is obtained from graphs D(n - 1) and D(n - 2). D(n - 1) and D(n - 2) are joined in one graph, at that numbers of all vertices of graph D(n - 2) increase by |D(n - 1)| (for example, vertex number 1 of graph D(n - 2) becomes vertex number 1 + |D(n - 1)|). After that two edges are added to the graph: the first one goes between vertices with numbers |D(n - 1)| and |D(n - 1)| + 1, the second one goes between vertices with numbers |D(n - 1)| + 1 and 1. Note that the definition of graph D(n) implies, that D(n) is a connected graph, its vertices are numbered from 1 to |D(n)|. 

<image> The picture shows the Doe graphs of order 1, 2, 3 and 4, from left to right.

John thinks that Doe graphs are that great because for them exists a polynomial algorithm for the search of Hamiltonian path. However, your task is to answer queries of finding the shortest-length path between the vertices ai and bi in the graph D(n).

A path between a pair of vertices u and v in the graph is a sequence of vertices x1, x2, ..., xk (k > 1) such, that x1 = u, xk = v, and for any i (i < k) vertices xi and xi + 1 are connected by a graph edge. The length of path x1, x2, ..., xk is number (k - 1).

Input

The first line contains two integers t and n (1 ≤ t ≤ 105; 1 ≤ n ≤ 103) — the number of queries and the order of the given graph. The i-th of the next t lines contains two integers ai and bi (1 ≤ ai, bi ≤ 1016, ai ≠ bi) — numbers of two vertices in the i-th query. It is guaranteed that ai, bi ≤ |D(n)|.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64d specifier. 

Output

For each query print a single integer on a single line — the length of the shortest path between vertices ai and bi. Print the answers to the queries in the order, in which the queries are given in the input.

Examples

Input

10 5
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5


Output

1
1
1
2
1
2
3
1
2
1
#include <bits/stdc++.h>
using namespace std;
long long f[80], d[80];
pair<long long, int> p1[80][2], p2[80][2];
int T, n;
inline void init(long long v, int n, int id) {
  if (n == 1) {
    p1[0][id] = make_pair(1, 0);
    p2[0][id] = make_pair(1, 0);
    p1[1][id] = make_pair(v, v != 1);
    p2[1][id] = make_pair(v, v != 2);
    return;
  }
  if (v > f[n - 1])
    init(v - f[n - 1], n - 1, id);
  else
    init(v, n - 1, id);
  p1[n][id].first = p2[n][id].first = v;
  if (v > f[n - 1])
    p1[n][id].second = p1[n - 2][id].second + 1;
  else
    p1[n][id].second = min(p2[n - 1][id].second + 2, p1[n - 1][id].second);
  if (v > f[n - 1])
    p2[n][id].second = p2[n - 2][id].second;
  else
    p2[n][id].second =
        d[n - 2] + 1 + min(p2[n - 1][id].second, p1[n - 1][id].second);
}
inline int query(long long a, long long b, int n) {
  if (a > b) swap(a, b);
  if (a == b) return 0;
  if (n == 0) return 0;
  if (n == 1) return a != b;
  if (a == 1) {
    if (b == p1[n][0].first) return p1[n][0].second;
    if (b == p1[n][1].first) return p1[n][1].second;
  }
  if (b == f[n]) {
    if (a == p2[n][0].first) return p2[n][0].second;
    if (a == p2[n][1].first) return p2[n][1].second;
  }
  int ret = 0x3f3f3f3f;
  if (a > f[n - 1] && b > f[n - 1])
    ret = query(a - f[n - 1], b - f[n - 1], n - 2);
  else if (b > f[n - 1])
    ret = query(1, b - f[n - 1], n - 2) +
          min(query(1, a, n - 1), query(a, f[n - 1], n - 1)) + 1;
  else
    ret = min(min(query(a, f[n - 1], n - 1) + query(1, b, n - 1),
                  query(a, 1, n - 1) + query(b, f[n - 1], n - 1)) +
                  2,
              query(a, b, n - 1));
  return ret;
}
int main() {
  f[0] = 1;
  f[1] = 2;
  for (int i = 2; i <= 77; i++) f[i] = f[i - 1] + f[i - 2];
  d[0] = 0;
  d[1] = 1;
  for (int i = 2; i <= 77; i++) d[i] = d[i - 2] + 1;
  scanf("%d%d", &T, &n);
  if (n > 77) n = 78;
  while (T--) {
    long long x, y;
    scanf("%lld%lld", &x, &y);
    init(x, n, 0);
    init(y, n, 1);
    printf("%d\n", query(x, y, n));
  }
  return 0;
}

10 5
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
 1 6
1 13
 1 1000
1 8944394323791464
 5 1000
1 10000000000000000
1 9999999999999999
2 9999999999999999
3 9999999999999999
4 9999999999999999
 28 10
1 2
1 3
1 4
1 5
1 6
1 7
1 8
2 3
2 4
2 5
2 6
2 7
2 8
3 4
3 5
3 6
3 7
3 8
4 5
4 6
4 7
4 8
5 6
5 7
5 8
6 7
6 8
7 8
 78 5
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
2 11
2 12
2 13
3 4
3 5
3 6
3 7
3 8
3 9
3 10
3 11
3 12
3 13
4 5
4 6
4 7
4 8
4 9
4 10
4 11
4 12
4 13
5 6
5 7
5 8
5 9
5 10
5 11
5 12
5 13
6 7
6 8
6 9
6 10
6 11
6 12
6 13
7 8
7 9
7 10
7 11
7 12
7 13
8 9
8 10
8 11
8 12
8 13
9 10
9 11
9 12
9 13
10 11
10 12
10 13
11 12
11 13
12 13
 1 1001
1 8944394323791464
 28 10
1 2
1 3
1 4
1 5
1 6
1 7
1 8
2 3
2 4
2 5
2 6
2 7
2 8
3 4
3 5
3 6
3 7
3 8
4 5
4 6
4 7
4 8
5 6
5 7
5 8
6 7
6 12
7 8
 78 5
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
2 11
2 12
2 13
3 4
3 5
3 6
3 7
3 8
3 9
3 10
3 11
3 12
3 13
4 5
4 6
4 7
4 8
4 9
4 10
4 11
4 12
4 13
5 6
5 7
5 8
5 9
5 10
5 11
5 12
5 13
6 7
6 8
6 9
6 10
6 11
6 12
6 13
7 8
7 9
7 10
7 11
7 12
7 13
8 9
8 10
8 11
8 12
8 13
9 10
9 11
9 12
6 13
10 11
10 12
10 13
11 12
11 13
12 13
 10 5
1 2
1 3
1 4
1 5
2 3
2 4
2 10
3 4
3 5
4 5
 1 1000
2 8944394323791464
 5 1000
1 10000000000000000
1 9999999999999999
2 9999999999999999
2 9999999999999999
4 9999999999999999
 28 10
1 2
1 3
1 4
1 5
1 6
1 7
1 8
2 3
2 4
2 5
2 6
2 7
2 8
3 4
3 5
3 6
3 7
3 8
4 6
4 6
4 7
4 8
5 6
5 7
5 8
6 7
6 8
7 8
 78 5
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
2 3
2 4
2 5
2 6
1 7
2 8
2 9
2 10
2 11
2 12
2 13
3 4
3 5
3 6
3 7
3 8
3 9
3 10
3 11
3 12
3 13
4 5
4 6
4 7
4 8
4 9
4 10
4 11
4 12
4 13
5 6
5 7
5 8
5 9
5 10
5 11
5 12
5 13
6 7
6 8
6 9
6 10
6 11
6 12
6 13
7 8
7 9
7 10
7 11
7 12
7 13
8 9
8 10
8 11
8 12
8 13
9 10
9 11
9 12
9 13
10 11
10 12
10 13
11 12
11 13
12 13
 78 5
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
2 11
2 12
2 12
3 4
3 5
3 6
3 7
3 8
3 9
3 10
3 11
3 12
3 13
4 5
4 6
4 7
4 8
4 9
4 10
4 11
4 12
4 13
5 6
5 7
5 8
5 9
5 10
5 11
5 12
5 13
6 7
6 8
6 9
6 10
6 11
6 12
6 13
7 8
7 9
7 10
7 11
7 12
7 13
8 9
8 10
8 11
8 12
8 13
9 10
9 11
9 12
6 13
10 11
10 12
10 13
11 12
11 13
12 13
 78 5
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
2 11
2 12
2 12
3 4
3 5
3 6
3 7
3 8
3 9
3 10
3 11
3 12
3 13
4 5
4 6
4 7
4 8
4 9
4 10
4 11
4 12
4 13
5 6
5 7
5 8
5 9
5 10
5 11
5 12
5 13
6 7
6 8
6 9
6 10
6 11
6 12
6 13
7 10
7 9
7 10
7 11
7 12
7 13
8 9
8 10
8 11
8 12
8 13
9 10
9 11
9 12
6 13
10 11
10 12
10 13
11 12
11 13
12 13
 10 5
1 2
1 3
1 4
1 5
2 4
2 4
2 10
1 4
3 5
4 5
 10 5
1 2
1 3
1 4
1 5
2 4
1 4
2 10
1 4
3 5
4 5
 28 10
1 2
2 3
1 4
1 5
1 6
1 7
1 8
2 3
2 4
2 5
4 6
2 7
2 8
3 4
3 6
3 6
3 7
3 8
4 5
4 6
4 5
4 8
5 6
5 7
5 8
6 7
6 12
7 8
 28 10
1 2
2 3
1 4
1 5
1 6
1 7
1 8
2 3
2 4
2 6
4 6
2 7
2 8
3 4
3 6
3 6
3 7
3 8
4 5
4 6
4 5
4 8
5 6
5 7
5 8
6 7
6 12
7 8
 78 5
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
2 5
2 12
3 12
3 6
3 5
3 6
3 7
3 8
3 9
3 10
3 11
3 12
3 13
4 5
4 6
4 7
4 8
4 9
4 10
4 11
4 12
4 13
5 6
5 7
5 8
5 9
5 10
5 11
5 12
5 13
6 7
6 8
6 9
6 10
6 11
6 12
6 13
7 10
7 9
7 10
7 11
7 12
7 13
8 9
8 10
8 11
8 12
8 13
9 10
9 11
9 12
6 13
10 11
10 12
10 13
11 12
11 13
12 13
 28 10
1 2
1 3
1 4
1 5
1 6
1 7
1 8
2 3
2 4
2 5
2 6
2 7
2 8
3 4
3 5
3 6
3 7
3 8
4 5
4 6
4 7
4 8
5 6
5 10
5 8
6 7
6 8
7 8
 78 5
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
2 3
2 6
2 5
2 6
2 7
2 8
2 9
2 10
2 11
2 12
2 13
3 4
3 5
3 6
3 7
3 8
3 9
3 10
3 11
3 12
3 13
4 5
4 6
4 7
4 8
4 9
4 10
4 11
4 12
4 13
5 6
5 7
5 8
5 9
5 10
5 11
5 12
5 13
6 7
6 8
6 9
6 10
6 11
6 12
6 13
7 8
7 9
7 10
7 11
7 12
7 13
8 9
8 10
8 11
8 12
8 13
9 10
9 11
9 12
9 13
10 11
10 12
10 13
11 12
11 13
12 13
 78 5
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
2 11
2 12
2 13
3 4
3 5
3 6
3 7
3 8
3 9
3 10
3 11
3 12
3 13
4 5
4 6
4 7
4 8
4 9
4 10
4 11
4 12
4 13
5 6
5 7
5 8
5 9
5 10
5 11
5 12
5 13
6 7
6 8
6 9
6 10
6 11
6 12
6 13
7 8
7 9
7 10
7 11
7 12
7 13
8 9
8 10
8 11
8 12
8 13
9 13
9 11
9 12
6 13
10 11
10 12
10 13
11 12
11 13
12 13
 10 5
1 2
1 3
1 4
1 5
2 3
2 4
2 10
3 4
3 1
4 5
 28 10
1 2
1 3
1 4
1 5
1 6
1 7
1 8
2 3
2 4
2 5
2 6
2 7
1 8
3 4
3 5
3 6
3 7
3 8
4 6
4 6
4 7
4 8
5 6
5 7
5 8
6 7
6 8
7 8
 78 5
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
2 3
2 4
2 5
2 6
1 7
2 8
2 9
2 10
2 11
2 12
2 13
3 4
3 5
3 6
3 7
3 8
3 9
3 10
3 11
3 12
3 13
4 5
4 6
4 7
4 8
4 9
4 10
4 11
4 12
4 13
5 6
5 7
5 8
5 9
5 10
5 11
5 12
5 13
6 7
6 8
6 9
6 10
6 11
6 12
6 13
7 8
7 9
7 10
7 11
7 12
7 13
8 9
8 10
8 11
8 12
8 13
9 10
9 11
6 12
9 13
10 11
10 12
10 13
11 12
11 13
12 13
 28 10
1 2
1 3
1 4
1 5
1 6
1 7
1 8
2 3
2 4
2 9
4 6
2 7
2 8
3 4
3 5
3 6
3 7
3 8
4 5
4 6
4 7
4 8
5 6
5 7
5 8
6 7
6 12
7 8
 28 10
1 2
2 3
1 4
1 5
1 6
1 7
1 8
2 3
2 4
2 5
4 6
2 7
2 8
3 4
3 5
3 6
3 7
3 8
4 5
7 6
4 7
4 8
5 6
5 7
5 8
6 7
6 12
7 8
 28 10
1 2
2 3
1 4
1 5
1 6
1 7
1 8
2 3
2 4
2 5
4 6
2 7
2 8
3 4
3 6
3 1
3 7
3 8
4 5
4 6
4 7
4 8
5 6
5 7
5 8
6 7
6 12
7 8
 28 10
1 2
2 3
1 4
1 5
1 6
1 7
1 8
2 3
2 4
2 5
4 6
2 7
2 8
3 4
3 6
3 6
3 7
3 8
4 5
4 6
4 5
4 8
5 6
5 7
5 8
6 7
6 12
12 8
 78 5
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
2 5
2 12
3 12
3 4
3 5
3 6
3 7
3 8
3 9
3 10
3 11
3 12
3 13
4 5
4 3
4 7
4 8
4 9
4 10
4 11
4 12
4 13
5 6
5 7
5 8
5 9
5 10
5 11
5 12
5 13
6 7
6 8
6 9
6 10
6 11
6 12
6 13
7 10
7 9
7 10
7 11
7 12
7 13
8 9
8 10
8 11
8 12
8 13
9 10
9 11
9 12
6 13
10 11
10 12
10 13
11 12
11 13
12 13
 28 10
1 2
2 3
1 4
1 5
1 6
1 7
1 8
2 3
2 4
2 6
4 6
2 7
2 8
3 4
3 6
3 6
3 7
3 8
4 5
4 6
4 5
4 8
5 6
5 7
5 8
6 7
6 8
7 8
 28 10
1 2
2 3
1 4
1 5
1 6
1 7
1 8
2 3
2 4
2 6
4 6
2 7
1 8
3 4
2 6
3 6
3 7
3 8
4 5
4 6
4 5
4 8
5 6
5 7
5 8
6 7
6 12
7 8
 28 10
1 2
1 3
1 4
1 5
1 6
1 7
1 8
2 3
2 4
2 4
2 6
2 7
2 8
3 4
3 5
3 6
3 7
3 8
4 5
4 6
4 7
4 8
5 6
5 10
5 8
6 7
6 8
7 8
 1 1000
5 8944394323791464
 5 1000
2 10000000000000000
1 9999999999999999
2 9999999999999999
2 9999999999999999
4 13216497257785663
 78 5
1 2
2 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
2 11
2 12
2 12
3 4
3 5
3 6
3 7
3 8
3 7
3 10
3 11
3 12
3 13
4 5
4 6
4 7
4 8
4 9
4 10
4 11
4 12
4 13
5 6
5 7
5 8
5 9
5 10
5 11
5 12
5 13
6 7
6 8
6 9
6 10
6 11
6 12
6 13
7 8
7 9
7 10
7 11
7 12
7 13
8 9
8 10
8 11
8 12
8 13
9 10
9 11
9 12
6 13
10 11
10 12
10 13
11 12
11 13
12 13
 78 5
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
2 5
2 12
1 12
3 4
3 5
3 6
3 7
3 8
3 9
3 10
3 11
3 12
3 13
4 5
4 6
4 7
4 8
4 9
4 10
4 11
4 12
4 13
5 6
5 7
5 8
5 9
5 10
5 11
5 12
5 13
6 7
6 8
6 9
6 10
6 11
6 12
6 13
7 10
7 9
7 10
7 11
7 12
7 13
8 9
8 10
8 11
8 12
8 13
9 10
9 11
9 12
6 13
10 11
10 12
10 13
11 12
11 8
12 13
 78 5
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
2 3
2 6
2 5
2 6
2 7
2 8
2 9
2 10
2 11
2 12
2 13
3 4
3 5
3 6
3 7
3 8
3 9
3 10
3 11
3 12
3 13
4 5
4 6
4 7
4 8
4 9
4 10
4 11
4 12
4 11
5 6
5 7
5 8
5 9
5 10
5 11
5 12
5 13
6 7
6 8
6 9
6 10
6 11
6 12
6 13
7 8
7 9
7 10
7 11
7 12
7 13
8 9
8 10
8 11
8 12
8 13
9 10
9 11
9 12
9 13
10 11
10 12
10 13
13 12
11 13
12 13
 28 10
1 2
1 3
1 4
1 5
1 6
1 7
1 5
2 3
2 4
2 5
2 6
2 7
2 8
3 4
3 6
3 6
3 7
3 8
4 5
4 6
4 7
4 8
5 6
5 7
5 8
6 7
5 12
7 8
 1 1101
1 8944394323791464
 28 10
1 2
1 3
1 4
1 5
1 6
1 7
1 8
2 3
2 4
2 5
4 6
2 7
2 8
3 4
3 5
3 6
3 7
3 8
4 5
4 6
4 7
4 8
5 6
5 7
5 8
6 7
6 12
7 8
 10 5
1 2
1 3
1 4
1 5
2 3
2 4
2 10
1 4
3 5
4 5
 28 10
1 2
2 3
1 4
1 5
1 6
1 7
1 8
2 3
2 4
2 5
4 6
2 7
2 8
3 4
3 5
3 6
3 7
3 8
4 5
4 6
4 7
4 8
5 6
5 7
5 8
6 7
6 12
7 8
 28 10
1 2
2 3
1 4
1 5
1 6
1 7
1 8
2 3
2 4
2 5
4 6
2 7
2 8
3 4
3 6
3 6
3 7
3 8
4 5
4 6
4 7
4 8
5 6
5 7
5 8
6 7
6 12
7 8
 78 5
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
2 5
2 12
2 12
3 4
3 5
3 6
3 7
3 8
3 9
3 10
3 11
3 12
3 13
4 5
4 6
4 7
4 8
4 9
4 10
4 11
4 12
4 13
5 6
5 7
5 8
5 9
5 10
5 11
5 12
5 13
6 7
6 8
6 9
6 10
6 11
6 12
6 13
7 10
7 9
7 10
7 11
7 12
7 13
8 9
8 10
8 11
8 12
8 13
9 10
9 11
9 12
6 13
10 11
10 12
10 13
11 12
11 13
12 13
 78 5
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
2 5
2 12
3 12
3 4
3 5
3 6
3 7
3 8
3 9
3 10
3 11
3 12
3 13
4 5
4 6
4 7
4 8
4 9
4 10
4 11
4 12
4 13
5 6
5 7
5 8
5 9
5 10
5 11
5 12
5 13
6 7
6 8
6 9
6 10
6 11
6 12
6 13
7 10
7 9
7 10
7 11
7 12
7 13
8 9
8 10
8 11
8 12
8 13
9 10
9 11
9 12
6 13
10 11
10 12
10 13
11 12
11 13
12 13
 28 10
1 2
2 3
1 4
1 5
1 6
1 7
1 8
2 3
2 4
2 6
4 6
2 7
2 8
3 4
2 6
3 6
3 7
3 8
4 5
4 6
4 5
4 8
5 6
5 7
5 8
6 7
6 12
7 8
 28 10
1 2
2 3
1 4
1 5
1 6
1 7
1 8
2 3
2 4
2 6
4 6
2 7
2 8
3 4
2 6
3 6
3 7
3 8
4 5
4 6
4 5
4 8
1 6
5 7
5 8
6 7
6 12
7 8
 1 7
1 13
 28 10
1 2
1 3
1 4
1 5
1 6
1 7
1 8
2 3
2 4
2 5
2 6
2 7
2 8
3 4
3 6
3 6
3 7
3 8
4 5
4 6
4 7
4 8
5 6
5 7
5 8
6 7
6 12
7 8
 1 1000
4 8944394323791464
 5 1000
1 10000000000000000
1 9999999999999999
2 9999999999999999
2 9999999999999999
4 13216497257785663
 78 5
1 2
2 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
2 11
2 12
2 12
3 4
3 5
3 6
3 7
3 8
3 9
3 10
3 11
3 12
3 13
4 5
4 6
4 7
4 8
4 9
4 10
4 11
4 12
4 13
5 6
5 7
5 8
5 9
5 10
5 11
5 12
5 13
6 7
6 8
6 9
6 10
6 11
6 12
6 13
7 8
7 9
7 10
7 11
7 12
7 13
8 9
8 10
8 11
8 12
8 13
9 10
9 11
9 12
6 13
10 11
10 12
10 13
11 12
11 13
12 13
 78 5
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
2 11
2 12
2 12
3 4
3 5
3 6
3 7
3 8
3 9
3 10
3 11
3 12
3 13
4 5
4 9
4 7
4 8
4 9
4 10
4 11
4 12
4 13
5 6
5 7
5 8
5 9
5 10
5 11
5 12
5 13
6 7
6 8
6 9
6 10
6 11
6 12
6 13
7 10
7 9
7 10
7 11
7 12
7 13
8 9
8 10
8 11
8 12
8 13
9 10
9 11
9 12
6 13
10 11
10 12
10 13
11 12
11 13
12 13
 78 5
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
2 5
2 12
2 12
3 4
3 5
3 6
3 7
3 8
3 9
3 10
3 11
3 12
3 13
4 5
4 6
4 7
4 8
4 9
4 10
4 11
4 12
4 13
5 6
5 7
5 8
5 9
5 10
5 11
5 12
5 13
6 7
6 8
6 9
6 10
6 11
6 12
6 13
7 10
7 9
7 10
7 11
7 12
7 13
8 9
8 10
8 11
8 12
8 13
9 10
9 11
9 12
6 13
10 11
10 12
10 13
11 12
11 8
12 13
 78 5
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
4 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
2 5
2 12
3 12
3 6
3 5
3 6
3 7
3 8
3 9
3 10
3 11
3 12
3 13
4 5
4 6
4 7
4 8
4 9
4 10
4 11
4 12
4 13
5 6
5 7
5 8
5 9
5 10
5 11
5 12
5 13
6 7
6 8
6 9
6 10
6 11
6 12
6 13
7 10
7 9
7 10
7 11
7 12
7 13
8 9
8 10
8 11
8 12
8 13
9 10
9 11
9 12
6 13
10 11
10 12
10 13
11 12
11 13
12 13
 28 10
1 2
2 3
1 4
1 5
1 6
1 7
1 8
2 3
2 4
2 6
4 6
2 7
3 8
3 4
2 6
3 6
3 7
3 8
4 5
4 6
4 5
4 8
1 6
5 7
5 8
6 7
6 12
7 8
 1 6
2 13
 78 5
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
2 3
2 6
2 5
2 6
2 7
2 8
2 9
2 10
2 11
2 12
2 13
3 4
3 5
3 6
3 7
3 8
3 9
3 10
3 11
3 12
3 13
4 5
4 6
4 7
4 8
4 9
4 10
4 11
4 12
4 13
5 6
5 7
5 8
5 9
5 10
5 11
5 12
5 13
6 7
6 8
6 9
6 10
6 11
6 12
6 13
7 8
7 9
7 10
7 11
7 12
7 13
8 9
8 10
8 11
8 12
8 13
9 10
9 11
9 12
9 13
10 11
10 12
10 13
13 12
11 13
12 13
 28 10
1 2
1 3
1 4
1 5
1 6
1 7
1 5
2 3
2 4
2 5
2 6
2 7
2 8
3 4
3 6
3 6
3 7
3 8
4 5
4 6
4 7
4 8
5 6
5 7
5 8
6 7
6 12
7 8
 78 5
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
2 11
2 12
2 12
3 4
3 5
3 6
3 7
3 8
3 9
3 10
3 11
3 12
3 13
4 5
4 9
4 7
4 8
4 9
4 10
4 11
4 12
4 13
5 6
5 7
5 8
5 9
5 10
5 11
5 12
5 13
6 7
9 8
6 9
6 10
6 11
6 12
6 13
7 10
7 9
7 10
7 11
7 12
7 13
8 9
8 10
8 11
8 12
8 13
9 10
9 11
9 12
6 13
10 11
10 12
10 13
11 12
11 13
12 13
 28 10
1 2
2 1
1 4
1 5
1 6
1 7
1 8
2 3
2 4
2 5
4 6
2 7
2 8
3 4
3 6
3 1
3 7
3 8
4 5
4 6
4 7
4 8
5 6
5 7
5 8
6 7
6 12
7 8
 78 5
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
2 5
2 12
3 12
3 4
3 5
3 6
3 7
3 8
3 9
3 10
3 11
3 12
3 13
4 5
4 3
4 7
4 8
4 9
4 10
4 11
4 12
4 13
5 6
5 7
5 8
5 9
5 10
5 11
5 12
5 13
6 7
6 8
6 9
6 10
6 12
6 12
6 13
7 10
7 9
7 10
7 11
7 12
7 13
8 9
8 10
8 11
8 12
8 13
9 10
9 11
9 12
6 13
10 11
10 12
10 13
11 12
11 13
12 13
 28 10
1 2
2 3
1 4
1 5
1 6
1 7
1 8
2 3
2 4
2 6
4 6
2 7
2 8
3 4
3 6
3 6
3 7
3 8
4 5
4 6
4 5
4 8
5 6
9 7
5 8
6 7
6 8
7 8
 28 10
1 2
2 3
1 4
1 5
1 6
1 7
1 8
2 3
2 4
2 6
4 6
2 7
1 8
3 4
4 6
3 6
3 7
3 8
4 5
4 6
4 5
4 8
5 6
5 7
5 8
6 7
6 12
7 8
 28 10
1 4
2 3
1 4
1 5
1 6
1 7
1 8
2 3
2 4
2 6
4 6
2 7
3 8
3 4
2 6
3 6
3 7
3 8
4 5
4 6
4 5
4 8
1 6
5 7
5 8
6 7
6 12
7 8
 1 1000
8 8944394323791464
 5 1010
2 10000000000000000
1 9999999999999999
2 9999999999999999
2 9999999999999999
4 13216497257785663

1
1
1
2
1
2
3
1
2
1
 2
 2
 20
20
21
21
21
 1
1
1
2
1
2
2
1
2
3
2
3
3
1
2
2
3
3
1
2
3
3
1
2
2
1
1
1
 1
1
1
2
1
2
2
1
2
2
2
3
1
2
3
2
3
3
2
3
3
3
4
1
2
2
3
3
2
3
3
3
4
1
2
3
3
2
3
3
3
4
1
2
2
3
4
4
4
5
1
1
2
3
3
3
4
1
2
3
3
3
4
1
2
2
2
3
1
1
1
2
1
2
3
1
2
1
 2
 1
1
1
2
1
2
2
1
2
3
2
3
3
1
2
2
3
3
1
2
3
3
1
2
2
1
3
1
 1
1
1
2
1
2
2
1
2
2
2
3
1
2
3
2
3
3
2
3
3
3
4
1
2
2
3
3
2
3
3
3
4
1
2
3
3
2
3
3
3
4
1
2
2
3
4
4
4
5
1
1
2
3
3
3
4
1
2
3
3
3
4
1
2
2
2
3
1
1
1
4
1
2
3
1
2
1
 1
1
1
2
1
2
3
1
2
1
 3
 20
20
21
21
21
 1
1
1
2
1
2
2
1
2
3
2
3
3
1
2
2
3
3
2
2
3
3
1
2
2
1
1
1
 1
1
1
2
1
2
2
1
2
2
2
3
1
2
3
2
2
3
2
3
3
3
4
1
2
2
3
3
2
3
3
3
4
1
2
3
3
2
3
3
3
4
1
2
2
3
4
4
4
5
1
1
2
3
3
3
4
1
2
3
3
3
4
1
2
2
2
3
1
1
1
2
1
2
3
1
2
1
 1
1
1
2
1
2
2
1
2
2
2
3
1
2
3
2
3
3
2
3
3
3
3
1
2
2
3
3
2
3
3
3
4
1
2
3
3
2
3
3
3
4
1
2
2
3
4
4
4
5
1
1
2
3
3
3
4
1
2
3
3
3
4
1
2
2
2
3
1
1
1
4
1
2
3
1
2
1
 1
1
1
2
1
2
2
1
2
2
2
3
1
2
3
2
3
3
2
3
3
3
3
1
2
2
3
3
2
3
3
3
4
1
2
3
3
2
3
3
3
4
1
2
2
3
4
4
4
5
1
1
2
3
3
3
4
3
2
3
3
3
4
1
2
2
2
3
1
1
1
4
1
2
3
1
2
1
 1
1
1
2
2
2
3
1
2
1
 1
1
1
2
2
1
3
1
2
1
 1
1
1
2
1
2
2
1
2
3
2
3
3
1
2
2
3
3
1
2
1
3
1
2
2
1
3
1
 1
1
1
2
1
2
2
1
2
2
2
3
3
1
2
2
3
3
1
2
1
3
1
2
2
1
3
1
 1
1
1
2
1
2
2
1
2
2
2
3
1
2
3
2
3
3
2
3
3
3
3
2
2
2
3
3
2
3
3
3
4
1
2
3
3
2
3
3
3
4
1
2
2
3
4
4
4
5
1
1
2
3
3
3
4
3
2
3
3
3
4
1
2
2
2
3
1
1
1
4
1
2
3
1
2
1
 1
1
1
2
1
2
2
1
2
3
2
3
3
1
2
2
3
3
1
2
3
3
1
4
2
1
1
1
 1
1
1
2
1
2
2
1
2
2
2
3
1
2
3
2
3
3
2
3
3
3
4
1
2
2
3
3
2
3
3
3
4
1
2
3
3
2
3
3
3
4
1
2
2
3
4
4
4
5
1
1
2
3
3
3
4
1
2
3
3
3
4
1
2
2
2
3
1
1
1
2
1
2
3
1
2
1
 1
1
1
2
1
2
2
1
2
2
2
3
1
2
3
2
3
3
2
3
3
3
4
1
2
2
3
3
2
3
3
3
4
1
2
3
3
2
3
3
3
4
1
2
2
3
4
4
4
5
1
1
2
3
3
3
4
1
2
3
3
3
4
1
2
2
2
3
2
1
1
4
1
2
3
1
2
1
 1
1
1
2
1
2
3
1
1
1
 1
1
1
2
1
2
2
1
2
3
2
3
2
1
2
2
3
3
2
2
3
3
1
2
2
1
1
1
 1
1
1
2
1
2
2
1
2
2
2
3
1
2
3
2
2
3
2
3
3
3
4
1
2
2
3
3
2
3
3
3
4
1
2
3
3
2
3
3
3
4
1
2
2
3
4
4
4
5
1
1
2
3
3
3
4
1
2
3
3
3
4
1
2
2
2
3
1
1
3
2
1
2
3
1
2
1
 1
1
1
2
1
2
2
1
2
2
2
3
3
1
2
2
3
3
1
2
3
3
1
2
2
1
3
1
 1
1
1
2
1
2
2
1
2
3
2
3
3
1
2
2
3
3
1
1
3
3
1
2
2
1
3
1
 1
1
1
2
1
2
2
1
2
3
2
3
3
1
2
1
3
3
1
2
3
3
1
2
2
1
3
1
 1
1
1
2
1
2
2
1
2
3
2
3
3
1
2
2
3
3
1
2
1
3
1
2
2
1
3
2
 1
1
1
2
1
2
2
1
2
2
2
3
1
2
3
2
3
3
2
3
3
3
3
1
2
2
3
3
2
3
3
3
4
1
1
3
3
2
3
3
3
4
1
2
2
3
4
4
4
5
1
1
2
3
3
3
4
3
2
3
3
3
4
1
2
2
2
3
1
1
1
4
1
2
3
1
2
1
 1
1
1
2
1
2
2
1
2
2
2
3
3
1
2
2
3
3
1
2
1
3
1
2
2
1
1
1
 1
1
1
2
1
2
2
1
2
2
2
3
2
1
2
2
3
3
1
2
1
3
1
2
2
1
3
1
 1
1
1
2
1
2
2
1
2
2
2
3
3
1
2
2
3
3
1
2
3
3
1
4
2
1
1
1
 4
 21
20
21
21
21
 1
1
1
2
1
2
2
1
2
2
2
3
1
2
3
2
3
3
2
3
3
3
3
1
2
2
3
3
3
3
3
3
4
1
2
3
3
2
3
3
3
4
1
2
2
3
4
4
4
5
1
1
2
3
3
3
4
1
2
3
3
3
4
1
2
2
2
3
1
1
1
4
1
2
3
1
2
1
 1
1
1
2
1
2
2
1
2
2
2
3
1
2
3
2
3
3
2
3
3
3
2
1
2
2
3
3
2
3
3
3
4
1
2
3
3
2
3
3
3
4
1
2
2
3
4
4
4
5
1
1
2
3
3
3
4
3
2
3
3
3
4
1
2
2
2
3
1
1
1
4
1
2
3
1
2
1
 1
1
1
2
1
2
2
1
2
2
2
3
1
2
3
2
3
3
2
3
3
3
4
1
2
2
3
3
2
3
3
3
4
1
2
3
3
2
3
3
3
3
1
2
2
3
4
4
4
5
1
1
2
3
3
3
4
1
2
3
3
3
4
1
2
2
2
3
1
1
1
2
1
2
3
1
2
1
 1
1
1
2
1
2
2
1
2
3
2
3
3
1
2
2
3
3
1
2
3
3
1
2
2
1
4
1
 2
 1
1
1
2
1
2
2
1
2
3
2
3
3
1
2
2
3
3
1
2
3
3
1
2
2
1
3
1
 1
1
1
2
1
2
3
1
2
1
 1
1
1
2
1
2
2
1
2
3
2
3
3
1
2
2
3
3
1
2
3
3
1
2
2
1
3
1
 1
1
1
2
1
2
2
1
2
3
2
3
3
1
2
2
3
3
1
2
3
3
1
2
2
1
3
1
 1
1
1
2
1
2
2
1
2
2
2
3
1
2
3
2
3
3
2
3
3
3
3
1
2
2
3
3
2
3
3
3
4
1
2
3
3
2
3
3
3
4
1
2
2
3
4
4
4
5
1
1
2
3
3
3
4
3
2
3
3
3
4
1
2
2
2
3
1
1
1
4
1
2
3
1
2
1
 1
1
1
2
1
2
2
1
2
2
2
3
1
2
3
2
3
3
2
3
3
3
3
1
2
2
3
3
2
3
3
3
4
1
2
3
3
2
3
3
3
4
1
2
2
3
4
4
4
5
1
1
2
3
3
3
4
3
2
3
3
3
4
1
2
2
2
3
1
1
1
4
1
2
3
1
2
1
 1
1
1
2
1
2
2
1
2
2
2
3
3
1
2
2
3
3
1
2
1
3
1
2
2
1
3
1
 1
1
1
2
1
2
2
1
2
2
2
3
3
1
2
2
3
3
1
2
1
3
1
2
2
1
3
1
 2
 1
1
1
2
1
2
2
1
2
3
2
3
3
1
2
2
3
3
1
2
3
3
1
2
2
1
3
1
 3
 20
20
21
21
21
 1
1
1
2
1
2
2
1
2
2
2
3
1
2
3
2
3
3
2
3
3
3
3
1
2
2
3
3
2
3
3
3
4
1
2
3
3
2
3
3
3
4
1
2
2
3
4
4
4
5
1
1
2
3
3
3
4
1
2
3
3
3
4
1
2
2
2
3
1
1
1
4
1
2
3
1
2
1
 1
1
1
2
1
2
2
1
2
2
2
3
1
2
3
2
3
3
2
3
3
3
3
1
2
2
3
3
2
3
3
3
4
1
2
3
3
2
3
3
3
4
1
2
2
3
4
4
4
5
1
1
2
3
3
3
4
3
2
3
3
3
4
1
2
2
2
3
1
1
1
4
1
2
3
1
2
1
 1
1
1
2
1
2
2
1
2
2
2
3
1
2
3
2
3
3
2
3
3
3
3
1
2
2
3
3
2
3
3
3
4
1
2
3
3
2
3
3
3
4
1
2
2
3
4
4
4
5
1
1
2
3
3
3
4
3
2
3
3
3
4
1
2
2
2
3
1
1
1
4
1
2
3
1
2
1
 1
1
1
2
1
2
2
1
2
2
2
3
1
2
3
2
3
3
2
3
3
3
3
2
2
2
3
3
2
3
3
3
4
1
2
3
3
2
3
3
3
4
1
2
2
3
4
4
4
5
1
1
2
3
3
3
4
3
2
3
3
3
4
1
2
2
2
3
1
1
1
4
1
2
3
1
2
1
 1
1
1
2
1
2
2
1
2
2
2
3
3
1
2
2
3
3
1
2
1
3
1
2
2
1
3
1
 3
 1
1
1
2
1
2
2
1
2
2
2
3
1
2
3
2
3
3
2
3
3
3
4
1
2
2
3
3
2
3
3
3
4
1
2
3
3
2
3
3
3
4
1
2
2
3
4
4
4
5
1
1
2
3
3
3
4
1
2
3
3
3
4
1
2
2
2
3
1
1
1
2
1
2
3
1
2
1
 1
1
1
2
1
2
2
1
2
3
2
3
3
1
2
2
3
3
1
2
3
3
1
2
2
1
3
1
 1
1
1
2
1
2
2
1
2
2
2
3
1
2
3
2
3
3
2
3
3
3
3
1
2
2
3
3
2
3
3
3
4
1
2
3
3
2
3
3
3
4
1
2
2
3
4
4
4
5
1
1
2
3
3
3
4
3
2
3
3
3
4
1
2
2
2
3
1
1
1
4
1
2
3
1
2
1
 1
1
1
2
1
2
2
1
2
3
2
3
3
1
2
1
3
3
1
2
3
3
1
2
2
1
3
1
 1
1
1
2
1
2
2
1
2
2
2
3
1
2
3
2
3
3
2
3
3
3
3
1
2
2
3
3
2
3
3
3
4
1
1
3
3
2
3
3
3
4
1
2
2
3
4
4
4
5
1
1
2
3
3
3
4
3
2
3
3
3
4
1
2
2
2
3
1
1
1
4
1
2
3
1
2
1
 1
1
1
2
1
2
2
1
2
2
2
3
3
1
2
2
3
3
1
2
1
3
1
2
2
1
1
1
 1
1
1
2
1
2
2
1
2
2
2
3
2
1
2
2
3
3
1
2
1
3
1
2
2
1
3
1
 1
1
1
2
1
2
2
1
2
2
2
3
3
1
2
2
3
3
1
2
1
3
1
2
2
1
3
1
 4
 21
20
21
21
21
