## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

## [Solution] KBG and GN-Theory CodeChef Solution

After solving some Graph Theory related problems KBG challenged Sameer to solve the following problem.

There is an undirected graph consisting of $N$ vertices numbered from $1$ to $N$.

For every pair of vertices $u$ and $v$ $\left(u\ne v\right)$ in the graph, there is a undirected weighted edge between $u$ and $v$ if and only if $u$ divides $v$, with weight $\frac{v}{u}$. Note that such a graph will not have self loops or multiple edges.

You must answer $Q$ queries. In each query you are given two vertices $u$ and $v$. You must find the

Solution Click Below:-  👉
👇👇👇👇👇

minimum distance from vertex $u$ to vertex $v$.

### Input Format

• The first line contains a single integer $T$ — the number of test cases. Then the test cases follow.
• The first line of each test case contains two integers $N$ and $Q$ — the number of vertices and the number of queries.

• The next $Q$ lines contain two space-separated integers $u$ and $v$ — vertices corresponding to the query.

### Output Format

For each test case, print $Q$ lines — the answers to the $Q$ queries.

### Constraints

• $1\le T\le {10}^{5}$
• $1\le N\le {10}^{5}$
• $1\le Q\le {10}^{5}$
• $1\le u,v\le N$
• The sum of $N$ over all test cases does not exceed ${10}^{5}$.
• The sum of $Q$ over all test cases does not exceed