For Solution

Given two constructive numbers BB and CC, what’s the minimal constructive worth of AA, such that ABA⋅B is divisible by CC.

Right here, ABA⋅B denotes the worth obtained when AA is multiplied by BB.

The product mystery solution codechef

• The first line will include an integer TT – variety of take a look at circumstances. Then the take a look at circumstances observe.
• The first and solely line of every take a look at case incorporates two integers BB and CC.

Output Format

For every take a look at case, output the minimal worth of AA such that ABA⋅B is divisible by CC.

Constraints

• 1T1051≤T≤105
• 1B,C1091≤B,C≤109

The product mystery solution codechef

2
2 4
8 12


Pattern Output 1

2
3


The product mystery solution codechef

Check case 11: We now have B=2B=2 and C=4C=4. If we select A=2A=2, then AB=4A⋅B=4, which is divisible by 44. Be aware that that is minimal constructive worth of AA, such that ABA⋅B is divisible by CC.

Check case 22: We now have B=8B=8 and C=12C=12. If we select A=3A=3, then AB=24A⋅B=24, which is divisible by 1212. Be aware that that is minimal constructive worth of AA, such that ABA⋅B is divisible by CC.