Broken Communication Towers

In 2050, countless communication towers stand on the Pusan National University campus. Originally, any two different towers could communicate one to one. On a day of heavy rain, students who disliked the towers secretly smashed the integer processing part of every tower with a hammer. Repairing the towers would take 1000 years, so for now the broken towers will be used. The broken towers have the following properties.

• Each tower has a natural number identifier starting from 1, and the list is unbounded. The identifier of tower $i$ is $i$.
• For towers $a$ and $b$, direct communication is possible if the pair $(a, b)$ is a divisor relation. A divisor relation means that when the larger number of the pair is divided by the smaller, the remainder is 0.
• The direct communication cost between tower 1 and a tower with an even identifier is 2. The direct communication cost of every other communication is 1.
• If tower $a$ can communicate with tower $c$, and tower $c$ can communicate with tower $b$, then towers $a$ and $b$ can communicate through tower $c$. The communication cost is the sum of the costs of each direct communication.

Sanjini, the president of Pusan National University, wants to reduce communication costs. Sanjini decides to write a program that finds the communication path with the minimum cost between any towers $a$ and $b$. To simplify the management of communication logs, Sanjini also wants the path with the smallest sum of tower identifiers on the path when several paths have the minimum cost. The member of the algorithm club PULSE was threatened with dissolution if the program was not finished within 3 hours, and the work was handed to the club. Under the input constraints, the communication path that satisfies the path selection conditions is unique for any valid input.