Group QQ Speed 数学/思维

Input file: standard Input Output file: standard Output Time limit: 1 second Memory limit: 512 megabytes

Problem Description

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.

Input

The first line contains a single integer T (1 ≤ T ≤ 105 ) — the number of test cases. Each of the next T lines contains two integers n and m (1 ≤ n, m ≤ 109 , m | n).

Output

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

Example

Standard IputStandard Oputput248 84 233

Solution

😀 算法标签：数学/思维

1. 如果所有人在同一组里，由于每个人都可能会禁掉不同的地图，因此我们应该有 n + 1 n + 1 n+1张地图；
2. 如果每个人单独一组，则需要2张图；
3. 其余情况下，只需要3张地图即可满足题意。

#include 
#define itn int
#define ll long long
#define rnt register int
#define ull unsigned long long
#define IOF ios_base::sync_with_stdio(false)
#pragma GCC optimize("no-stack-protector")
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;

signed main(){
    IOF;
    int T = 0; cin >> T;
    while (T--){
        int n, m; cin >> n >> m;
        if (n == m) cout