Children of New Bernsburg love to play creative games. Once upon a time they decided to play a game called, "KING OF THE RING".

In this game they form a ring, a random child is selected and they start counting clockwise from that child until a fixed number (n, which is given at the starting of the game) is reached. When the count reaches n, the child on the nth spot is eliminated. The game continues again starting with the next child and the process continues until a single child remains.

Your aim is to print the position of the child which remains till last and hold the title King of the Ring.

Input

The first line of input contains number of children, m and the second line contains the fixed number, n, the factor by which children are eliminated.

Output

The output must print the position of the last child staying in the game.

Example

Input: 10 6 Output: 3q2

There are n bulbs in a row lighted during a marriage ceremony. A mischievous boy was passing from nearby when he had a naughty idea of breaking the bulbs. To make it interesting he does so in a pattern. He decides to smash every second lighted bulb on his first traversal, every third lighted bulb on his second traversal and so on. Getting exhausted at end he found that some of the bulbs remain lucky, not to be broken even during his indefinite process.

Your aim is to design a program which takes the input n i.e. number of bulbs and finds the position number of the still lighted bulbs.

Input

First line contains number of test cases t such that 0

The next t lines contain a single integer (n) each, such that 0

Output

The output should consist of t lines. Each line containing a single space separated positions of the lighted bulbs after the process.

Example

Input: 3 10 20 50 Output: 1 3 7 1 3 7 13 19 1 3 7 13 19 27 39 49