The Cheerful Monkey

A monkey has found a new game. It arranges $n$ cages, each holding exactly one animal, in a circle and hops across them. At the start every cage is closed.

The monkey begins on one cage and opens the cage it stands on. After that it always jumps forward by $d$ cages and opens the cage it lands on. The moment it jumps onto a cage that is already open, the monkey stops.

Every animal in an opened cage seizes the chance and escapes. Determine how many animals escape.

The first line contains one integer $z$ ($1 \le z \le 10^6$), the number of data sets. Each of the next $z$ lines describes one data set.

Each line contains two integers $n$ and $d$ ($1 \le n, d \le 10^9$): the number of cages and the length of the monkey's jump, respectively. ($d = 1$ means the monkey hops to the very next cage.)

For each data set, print on its own line the number of animals that escape.