Джон Доу решил, что в его честь должен быть назван какой-нибудь математический объект и изобрел графы Доу. Графы Доу — это семейство неориентированных графов, каждый из которых характеризуются единственным целым неотрицательным числом — порядком.
Граф Доу порядка 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. Графы Доу, по мнению Джона, хороши прежде всего тем, что для них существует полиномиальный алгоритм поиска Гамильтонова пути. Однако от Вас требуется отвечать на запросы о нахождении кратчайшего по длине пути между вершинами ai и bi в графе D(n).
Путь между парой вершин u и v в графе — это последовательность вершин x1, x2, ..., xk (k > 1) такая, что x1 = u, xk = v, и для любого i (i < k) вершины xi и xi + 1 связаны ребром графа. Длиной пути x1, x2, ..., xk называется число (k - 1).
Выходные данные
Для каждого запроса выведите в отдельной строке единственное целое число — длину кратчайшего пути между вершинами ai и bi. Ответы на запросы выводите в том порядке, в котором запросы заданы во входных данных.