Practice on Toph

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

Guti Khela

By ssavi1994 · Limits 1s, 1.0 GB

Guti Khela is an ancient village game of Bangladesh. This game is played between 2 players by digging tiny holes in the ground and keeping some pebbles inside the holes. We are presenting new and easier version of this game.

Lombu and Battu are two friends. They are participating in our new version of Guti Khela. After digging N small holes into the ground they will put X pebbles into Xth holes where X starts from 1 and ends at N. That means 1st hole contains 1 pebble, 2nd hole contains 2 pebbles and so on. It’s certain that each of the holes contains a distinct number of pebbles currently and no hole should be empty. The value of N should be maximized enough such that after putting pebbles into N holes according to the described manner the total number pebbles does not exceed S. S is the total number of pebbles they have.

They want to put all of the pebbles into the holes according to the described manner. That indicates some of the pebbles will go on a hole that already contains some pebbles. They have decided to put extra pebbles on a specific hole by making K groups of pebbles. That means they will divide extra pebbles into K group of a equal number of pebbles and then put them by the group into that specific hole. Remember, to put pebbles in the Xth hole you must put X pebbles each time.

Now the task is they had to choose where they should put those extra pebbles. If it is possible to figure out the hole then print it. If it is not possible to choose such holes then print “NO”. Otherwise print “Undetermined”.
They have challenged you to complete the task.

Input

The first line of each input file denotes the number of games Lombu and Battu will play and denoted by T (1 ≤ T ≤ 10000).

The next T lines contain two integers S and K (0 ≤ S, K < 2^64), the number of total pebbles and the number of groups they want to make.

Output

For each game, you need to print an integer which indicates the hole should be chosen if it is possible to choose a specific hole. If it is not possible to choose such holes then print “NO” (w/p quotes). Otherwise, print “Undetermined” (w/o quotes) if you have some difficulties in choosing a specific hole.

Sample

InputOutput
4
17 3 
17 2
17 1
13 7
NO
1
2
NO

In Game 1, they can dig 5 holes at most. So number of pebbles in each group are: 1 + 2 + 3 + 4 + 5 = 15 . Remaining pebbles 2. As you can’t make 3 groups of 2 pebbles so it’s not possible. Hence the answer is NO.


Discussion

Statistics


16% Solution Ratio

mahbubcsejuEarliest, Sep '17

subhashis_cseFastest, 276.9s

mahbubcsejuLightest, 131 kB

NirjhorShortest, 447B

Submit

Login to submit

Editorial

Do a Binary Search to figure out the maximum value of N such that sum of 0 - N &lt;= S. Find out the...

Related Contests

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