Джон Доу решил, что в его честь должен быть назван какой-нибудь математический объект и изобрел графы Доу. Графы Доу — это семейство неориентированных графов, каждый из которых характеризуются единственным целым неотрицательным числом — порядком.

Граф Доу порядка k обозначим за D(k), за |D(k)| обозначим количество вершин в графе D(k). Тогда определим графы Доу следующим образом:

• D(0) состоит из единственной вершины, которая имеет номер 1.
• D(1) состоит из двух вершин с номерами 1 и 2, соединенных ребром.
• D(n) для n ≥ 2 получается из графов D(n - 1) и D(n - 2). D(n - 1) и D(n - 2) объединяются в один граф, при этом номера всех вершин графа D(n - 2) увеличиваются на |D(n - 1)| (например, вершина номер 1 графа D(n - 2) становится вершиной номер 1 + |D(n - 1)|). После этого в граф добавляются два ребра: первое — между вершинами с номерами |D(n - 1)| и |D(n - 1)| + 1, второе — между вершинами с номерами |D(n - 1)| + 1 и 1. Обратите внимание, что из определения графа D(n) следует, что D(n) является связным графом, вершины которого пронумерованы от 1 до |D(n)|.

На рисунке изображены, слева-направо, графы Доу порядка 1, 2, 3 и 4.

Графы Доу, по мнению Джона, хороши прежде всего тем, что для них существует полиномиальный алгоритм поиска Гамильтонова пути. Однако от Вас требуется отвечать на запросы о нахождении кратчайшего по длине пути между вершинами a_i и b_i в графе D(n).

Путь между парой вершин u и v в графе — это последовательность вершин x₁, x₂, ..., x_k (k > 1) такая, что x₁ = u, x_k = v, и для любого i (i < k) вершины x_i и x_i + 1 связаны ребром графа. Длиной пути x₁, x₂, ..., x_k называется число (k - 1).