육각형 경로

최단 경로를 찾는 일은 트럭 운전사의 일상적인 과제입니다. 최단 경로로 달리면 비용을 아낄 수 있기 때문입니다. 또한 도로 공사 등으로 어떤 경로를 이용할 수 없게 될 경우를 대비해, 같은 길이의 다른 경로들을 알아 두는 것도 중요합니다.

어떤 지역을 나타내려면 그 지역의 지도를 모형화해야 합니다. 삼각형이나 사각형 기반 모형으로는 부족하다는 것이 밝혀져, 대신 육각형을 사용합니다. 벌집처럼 생긴 정육각형 격자에서, 임의의 한 칸을 1번으로 정하고 나선 모양으로 바깥쪽을 향해 돌아가며 번호를 매깁니다. 그러면 각 칸은 고유한 번호를 가지며, 모든 양의 정수는 정확히 한 칸을 가리킵니다.

두 칸은 한 변을 공유할 때에만 서로 이웃입니다. 무한한 격자에서 모든 칸은 정확히 여섯 개의 이웃을 가집니다. 예를 들어 2번 칸은 1, 3, 7, 8, 9, 10번 칸과 이웃합니다. 육각형 경로는 칸들의 비어 있지 않은 수열로, 마지막 칸을 제외한 각 칸이 바로 다음 칸과 이웃해야 합니다. 칸 $X$에서 칸 $Y$로 가는 경로는 $X$에서 시작해 $Y$에서 끝납니다. 경로의 길이는 (칸의 개수 $-$ 1)로, 경로를 따라 이동하는 걸음 수와 같습니다.

두 칸이 주어지면, 두 칸 사이 최단 경로의 길이와 그 길이를 갖는 서로 다른 경로의 개수를 구하세요. 두 경로는 한 칸이라도 다르면 서로 다른 것으로 봅니다. 두 경로가 서로 완전히 겹치지 않아야 하는 것은 아닙니다.

입력은 여러 개의 질의로 이루어지며, 각 질의는 한 줄에 주어집니다. 각 줄에는 공백으로 구분된 두 정수 $X$와 $Y$가 있으며, $1 \le X, Y \le 10^6$이고 $X \ne Y$입니다. 이는 서로 다른 두 칸을 나타냅니다. 마지막 줄에는 두 개의 0이 있으며, 이 줄은 입력의 끝을 알리는 것으로 질의가 아닙니다.

각 질의마다 한 줄씩 다음 문장을 출력합니다:

There are N routes of the shortest length L.

여기서 $L$은 칸 $X$와 $Y$ 사이 최단 경로의 길이, $N$은 그 길이를 갖는 서로 다른 경로의 개수입니다. 그러한 경로가 정확히 하나뿐이면 are와 routes 대신 is와 route를 사용합니다.