Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

The Feast

By rifatrraazz · Limits 1s, 256 MB

Nafia and Shishir like to feed pets. Today, Nafia has mm chocolates and Shishir has mm cakes for some cats and dogs. And they are hiring you for a special job.

  1. You will choose some cats and distribute some amount of chocolates among them equally such that you have exactly xx chocolates left for Nafia.

  2. Then, you will choose some dogs (not necessarily equal to the number of cats) and distribute some amount of cakes among them equally such that you have exactly xx cakes left for Shishir.

Note that you cannot break any chocolate or cake while distributing.

After that, you will arrange a feast where in each minute, exactly one cat will eat a portion of cake from one dog and that dog will eat a portion of chocolate from that cat simultaneously. The feast will last until every cat eats cake from every dog and every dog eats chocolate from every cat.

Nafia and Shishir want to watch the feast of the cats and dogs and they also want to eat the chocolates and cakes that you have kept for them. So, you have to choose the number of cats and dogs in such a way that both the number of cats and dogs should be greater than xx and the feast can continue for at least mm minutes. Finally, calculate the minimum duration (in minutes) of the feast.


The first line of the input will consist of an integer, tt (1t3000){(1 \le t \le 3000)}- the number of testcases.

Each testcase contains two space separated integers, mm and xx (0x<m109){(0 \le x < m \le 10^9 )}.


For each testcase -

  • If there is no way to choose such numbers of cats and dogs, print 1-1.

  • Otherwise, print an integer denoting the minimum duration of the feast.


15 3
7 5
11 3
24 4

In the first testcase, one possible scenario is you can choose 44 cats and 44 dogs and the feast will last for 1616 minutes which is minimum possible duration of the feast under the given condition.

In the second testcase, there are no such way to choose number of cats and dogs such that the feast can last at least 77 minutes.



    67% Solution Ratio

    Farhan20Earliest, 2w ago

    s_semicolonFastest, 0.4s

    swati_1952Lightest, 131 kB

    FrdhsnShortest, 829B


    Login to submit


    Let ccc be the number of cats and ddd is the number of dogs. As we’ve to distribute m−xm-xm−x chocol...

    Toph uses cookies. By continuing you agree to our Cookie Policy.