Diminishing Circle N people are standing in circle and play following game: they start with the first person, count K people clockwise, then the K+1-th person leaves the circle and the process starts all over, using the person clockwise of the last person removed as the starting point. For example when N = 9 and K = 3 people would leave in following order: 4, 8, 3, 9, 6, 5, 7, 2 Given N and K, find who wins the game if counting starts with person 1. Person indices are 1-based. The last person who is left is declared the winner. Input The input consists of a single integer T, the number of test cases. This is followed by T pairs of numbers N and K, all separated by whitespace. Output Print T whitespace-separated integers, the indices for each test case of the winner of the game. Constraints T = 20 1 ≤ N ≤ 10^12 1 ≤ K ≤ 10^4 Example input Code: 5 9 3 4 1 3 2 5 4 6 9 Example output Code: 1 1 2 2 2 File input: http://www.maxvessi.net/rebsite/fhc2011/diminishing_circle.txt