토너먼트

프로그래밍 토너먼트에 $n$명의 참가자가 출전합니다. 모든 참가자의 실력은 서로 다르므로, 두 참가자의 실력이 같은 경우는 없습니다.

매일 전날 살아남은 참가자들끼리 라운드를 진행합니다. 하루 동안 참가자들은 $k$명씩 여러 그룹으로 나뉩니다. $k$명이 모두 채워진 그룹에서는 실력이 가장 약한 한 명이 탈락하고, 나머지 $k - 1$명이 다음 날로 진출합니다. 인원이 $k$명에 못 미치는 그룹은 최대 한 개까지 생길 수 있으며, 그런 그룹에 속한 참가자는 전원 자동으로 다음 날로 진출합니다. 남은 인원이 $k$명 미만이 되어 $k$명짜리 그룹을 하나도 만들 수 없게 되면 토너먼트가 끝납니다.

날마다 참가자를 그룹으로 나누는 방식은 임의로 정해집니다. 가능한 모든 그룹 편성 방식을 통틀어, 토너먼트가 끝났을 때 살아남아 우승자가 될 수 있는 서로 다른 참가자가 몇 명인지 세어 주세요.

첫 번째 줄에 테스트 케이스의 개수 $z$ ($1 \le z \le 10^6$)가 주어집니다. 이어지는 $z$개의 줄에는 각각 두 정수 $n_i$와 $k_i$ ($2 \le n_i, k_i \le 10^9$)가 주어지며, 차례로 그 토너먼트의 참가자 수와 그룹 크기를 나타냅니다.

각 테스트 케이스마다 한 줄에 정수 하나를 출력합니다. 그 값은 해당 토너먼트에서 우승자가 될 수 있는 서로 다른 참가자의 수입니다.