Поиск кратчайшего маршрута является типичной задачей для водителя грузовика. Если грузовик движется по кратчайшему пути, это экономит деньги. Кроме того, важно знать альтернативные маршруты той же длины, в случае если основной маршрут недоступен, например, из-за некоторых дорожных работ.
Для описания области необходимо промоделировать ее карту. В ACM недавно обнаружили, что треугольные и прямоугольные модели областей являются недостаточными, поэтому решили использовать шестиугольники для описания карт. Клетки правильной шестиугольной сетки (например, сот) можно нумеровать, начиная с 1 (в любой клетке) и двигаться по спирали к другим клеткам. Таким образом, каждая ячейка однозначно идентифицируется своим номером. И наоборот, каждое положительное целое число определяет одну ячейку.
Две клетки называются соседними, если они имеют одну общую сторону. В бесконечной структуре каждая ячейка имеет ровно шесть соседей. Например, ячейка номер 2 соседствует с 1, 3, 7, 8, 9 и 10. Шестиугольный путь - это непустая последовательность ячеек, в которой каждая из них (кроме последней) является соседней с последующей. Шестиугольный путь между двумя ячейками X и Y - это путь, в котором X - первая ячейка последовательности, а Y - последняя. Длиной пути называется количество ячеек в нем минус один. Длина пути представляет собой количество шагов, необходимых для прохождения всего маршрута.
Вам следует найти длину кратчайшего маршрута между двумя клетками, а также общее количество взаимно различных маршрутов такой же длины. Различные маршруты должны различаться по крайней мере в одном члене последовательности, т.е. они не должны формировать полностью непересекающихся последовательности.
Входные данные состоят из нескольких тестов, каждый из которых расположен на отдельной строке. Строка содержит два целых числа X и Y (1 ≤ X, Y ≤ 1000000, X ≠ Y), разделенных пробелом. Числа задают две различные ячейки. За последним тестом следует строка из двух нулей, которая обозначает конец входных данных.
Для каждого теста вывести предложение "There are N routes of the shortest length L.". Замените L наименьшей длиной пути между ячейками X и Y. Замените N количеством различных путей той же самой длины. Если существует только один путь, то используйте слова "is" и "route" вместо "are" и "routes".