A jail has prisoners, and each prisoner has a unique id number, , ranging from to . There are sweets that must be distributed to the prisoners.
The jailer decides the fairest way to do this is by sitting the prisoners down in a circle (ordered by ascending ), and then, starting with some random , distribute one candy at a time to each sequentially numbered prisoner until all candies are distributed. For example, if the jailer picks prisoner , then his distribution order would be until all sweets are distributed.
But wait—there's a catch—the very last sweet is poisoned! Can you find and print the ID number of the last prisoner to receive a sweet so he can be warned?
The first line contains an integer, , denoting the number of test cases.
The subsequent lines each contain space-separated integers:
(the number of prisoners), (the number of sweets), and (the prisoner ID), respectively.
For each test case, print the ID number of the prisoner who receives the poisoned sweet on a new line.
Sample Input 0
2 5 2 15 2 2
Sample Output 0
In first query, there are prisoners and sweets. Distribution starts at ID number , so prisoner gets the first sweet and prisoner gets the second (last) sweet. Thus, we must warn prisoner about the poison, so we print on a new line.