Shortest Path in Divisibility Graph

You are given an undirected graph with n nodes numbered from 1 to n. There is an edge between node i and node j if and only if

\( \gcd(i, j) = \min(i,j) \) and \( \operatorname{lcm}(i, j) = \max(i,j) \)

This condition is equivalent to saying that if we let \( a = \min(i,j) \) and \( b = \max(i,j) \), then an edge exists if and only if \( a\mid b \). The weight of the edge is \( |i-j| \) (which equals \( b - a \)).

You need to answer q queries. In each query, you are given two nodes x and y and you must compute the shortest distance from x to y in the graph.

inputFormat

The first line contains two integers n and q --- the number of nodes and the number of queries.

Each of the next q lines contains two integers x and y representing a query to find the shortest path distance from node x to node y.

outputFormat

For each query, output a single integer --- the length of the shortest path from x to y.

sample

6 3
1 6
2 3
4 6

5
3
6