즐거운 원숭이

원숭이 한 마리가 새로운 놀이를 찾았습니다. 원숭이는 동물이 한 마리씩 들어 있는 우리 $n$개를 원형으로 늘어놓고 그 위를 뛰어다닙니다. 처음에 모든 우리는 닫혀 있습니다.

원숭이는 어떤 우리 하나에서 출발하며, 딛고 선 우리를 엽니다. 그 뒤로는 항상 $d$칸 앞의 우리로 뛰어가 도착한 우리를 엽니다. 이미 열려 있는 우리로 뛰어드는 순간 원숭이는 멈춥니다.

열린 우리 안의 동물은 모두 이 기회를 놓치지 않고 달아납니다. 달아나는 동물이 몇 마리인지 구하세요.

첫째 줄에 데이터 집합의 개수를 나타내는 정수 $z$ ($1 \le z \le 10^6$)가 주어집니다. 이어지는 $z$개의 줄에 각 데이터 집합이 하나씩 주어집니다.

각 줄에는 두 정수 $n$과 $d$ ($1 \le n, d \le 10^9$)가 공백으로 구분되어 주어집니다. 각각 우리의 개수와 원숭이가 한 번에 뛰어넘는 칸 수를 뜻합니다. ($d = 1$이면 원숭이는 바로 다음 우리로 뛰어갑니다.)

각 데이터 집합마다 달아나는 동물의 수를 한 줄에 하나씩 출력하세요.