WC 4.3 Game Of Thrones

To settle the fight for the Iron Throne, Tyrion comes up with a challenge

Many gold crates are available
Each crate contains 'N' gold coins
There are 'M' people in Westeros(the place where they live)
You are free to choose any number of gold crates
All gold coins from the chosen crates are distributed to 'M' people in such a way that each person gets equal number of gold coins
And one coin still remains unused

What is the minimum number of gold crates required for such a distribution?

Note 1 : The coins cannot be broken into fractions, number of coins in a crate cannot be changed
Note 2 : All coins in the chosen crates must be used(except one unused coin as mentioned in the problem statement)
Note 3 : You may choose to not give any coins to people(i.e. give 0 coins to each person but one coin still remains)


:: Input Specifications ::
First line of the input contains the number of test cases 'T'
The next 'T' lines each contain two space separated integers 'N' and 'M'

It is better to take input as a text file in your program

:: Constraints ::
0 < T <= 10^5
0 < N, M <= 10^12

:: Output Specifications ::
The answer for each test case is the required number of crates
If the answer is not possible for a test case, then answer for that test case is -1

Give your final answer as sum of answers for all the test cases
(it is guaranteed that absolute value of the final answer <= 10^18)

:: Examples ::

::Input::
3
5 7
4 9
3 1

::Output::
3
7
1

::Explanation::
For the first test case, we can take 3 gold crates each containing 5 gold coins
and distribute by giving 2 gold coins each to 7 people
This way each person gets equal no. of gold coins and 1 coin will remain unused
You can check that no smaller positive integral value of the number of crates will satisfy this condition

Similarly, for other cases

Input file link


Click to view hint

This challenge is worth 100 points.

You must be logged in to submit a solution

View ranklist for this challenge
About scoring and submission

Contact Us


Krish Shah : 9323115454

Kaustubh Khavnekar : 9769408039



Privacy Policy