Josephus problem is a theoretical problem related to a certain counting-out game. However, Narnal thought this problem is too easy for him, so he constructed a more complex Josephus problem as following.

There are \(n\) people standing in a circle indexing from \(1\) to \(n\), and each person in the circle holds a note marked with a positive integer. At first, given a positive integer \(m\), people count the number from one to the next starting from index \(1\) in clockwise (\(1, 2, \ldots, n, 1, 2, \ldots\)). When the counted number reaches \(m\), the corresponding person will be eliminated from the circle and yell the number in his/her note, denoted by \(k_{i}\), and then people restart counting from the next person targeting for number \(k_{i}\) until, eventually, only one person is left in the circle.

First line will be a positive integer \(T\), which is the number of test cases.

In each test case, the first line would be two integers \(n\) and \(m\), where \(n\) is the initial number of people, and \(m\) is the initial target counting number.

Then there will be a single line containing \(n\) integers, indicating the number on each person's note, from index \(1\) to index \(n\).

\(T \leq 100, 1 \leq n \leq 10^{4}\). \(m\) and each number on the notes will be in the range of \([1, 10^{8}]\). We guarantee that there are no more than \(20\) cases with \(n > 5 \times 10^{3}\).

For each case, output one line with one integer for the index of the remaining people.