#
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

Solution explanation link : link

### This challenge is worth 100 points.

### You must be logged in to submit a solution

View ranklist for this challenge

About scoring and submission