Shortest Path in an LCM Graph

You are given an undirected complete graph with \(10^{100}\) nodes numbered from \(1\) to \(10^{100}\). For every pair of distinct nodes \(u\) and \(v\), there is an edge connecting them with length \(\operatorname{lcm}(u,v)\), where \(\operatorname{lcm}(u,v)\) is the least common multiple of \(u\) and \(v\), i.e. the smallest positive integer divisible by both \(u\) and \(v\).

There are \(q\) queries. In each query, you are given two nodes \(x\) and \(y\) and you need to determine the length of the shortest path from node \(x\) to node \(y\).

Observation: Since the graph is complete, one can always travel directly from \(x\) to \(y\) with a cost of \(\frac{x \times y}{\gcd(x,y)}\) (because \(\operatorname{lcm}(x,y)=\frac{x\times y}{\gcd(x,y)}\)). However, notice that for any node \(d\) that divides both \(x\) and \(y\) (for example, \(1\)), the two-step journey \(x \to d \to y\) has a cost of \(x + y\) (since \(\operatorname{lcm}(x,d)=x\) and \(\operatorname{lcm}(d,y)=y\)). Therefore, the answer for each query is:

[ \min\left(\frac{x\times y}{\gcd(x,y)},; x+y\right). ]

Your task is to compute this minimum value for each query.

inputFormat

The first line contains a single integer \(q\) (the number of queries). Each of the next \(q\) lines contains two positive integers \(x\) and \(y\) separated by a space.

outputFormat

For each query, output a single line containing the length of the shortest path from \(x\) to \(y\).

sample

2
4 6
4 8

10
8