1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<iostream>
using namespace std;
int k;
int fun(int n){
    if(n == 1)
        return 0;
    else if(n <= k)
        return (fun(n - 1) + k) % n;
    else{
        if(fun(n - n / k) < n % k)
            return n - n % k + fun(n - n / k); 
        else
            return fun(n - n / k) - n % k + (fun(n - n / k) - n % k) / (k - 1);
    }
}
int main(){
    int T, N;
    cin >> T;
    while(T--){
        cin >> N >> k;
        cout << fun(N) << endl;
    }   
    return 0;
} 
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX