/*
    Name: NYOJ--94--cigarettes
    Copyright: 2017 日天大帝
    Date: 20/04/17 09:27
    Description: 水 题
*/
#include<iostream>
using namespace std;
int main()
{
    int N;
    cin>>N;
    while(N--){
        int n,k,m;
        cin>>n>>k;
        int last = n;
        while(n >= k){
            m = n%k;
            n /= k;
            last += n;
            n += m;
        }
        cout<<last<<endl;
    }
    ;
}