[Solution] The product mystery solution codechef

The product mystery solution codechef – Given two positive numbers BB and CC, what is the minimum positive value of AA, such that ABA⋅B is divisible by CC.

Here, ABA⋅B denotes the value obtained when AA is multiplied by BB.

The product mystery solution codechef

  • The first line will contain an integer TT – number of test cases. Then the test cases follow.
  • The first and only line of each test case contains two integers BB and CC.

Output Format

For each test case, output the minimum value 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

Sample Output 1 

2
3

The product mystery solution codechef

Test case 11: We have B=2B=2 and C=4C=4. If we choose A=2A=2, then AB=4A⋅B=4, which is divisible by 44. Note that this is minimum positive value of AA, such that ABA⋅B is divisible by CC.

Test case 22: We have B=8B=8 and C=12C=12. If we choose A=3A=3, then AB=24A⋅B=24, which is divisible by 1212. Note that this is minimum positive value of AA, such that ABA⋅B is divisible by CC.

Leave a Comment