408186: GYM103048 G Group QQ Speed

Cuber QQ likes QQ Speed, he always plays the game throughout all night, until early morning.

On a dark and gusty night, as usual, Cuber QQ was playing the $$$48$$$-player knockout round of QQ Speed, and it was his turn to "ban the map". He suddenly had an idea for the programming contest.

In each contest round, there are $$$n$$$ players. The gaming system will give all players $$$x$$$ maps, and each player can ban a map. After that, the gaming system will evenly, but not necessarily randomly, divide the players into $$$m$$$ groups ($$$m$$$ divides $$$n$$$). Every player in the same group must race on the same map, and different groups can either race on the same map or not. If one of the players in the group have banned a map, this map cannot be used by this group any more. Now, Cuber QQ wants to know the minimal number of maps the gaming system needs to provide to the players, and these maps can ensure having at least one grouping scheme in any case.

The first line contains a single integer $$$T$$$ ($$$1\le T\le 10^5$$$) — the number of test cases.

Each of the next $$$T$$$ lines contains two integers $$$n$$$ and $$$m$$$ ($$$1\le n,m\le 10^9,m\mid n$$$).

For each test case, output one line containing one integer which is the answer.

2
48 8
4 2

3
3