const int INF = 1e14 + 7;
const ld EPS = 1e-10;

signed main() {
    seriy();
    int t;
    cin >> t;
    while(t--) {
        int m, k;
        cin >> m >> k;
        int l = 0, r = INF;
        ld p = m, q = k;
        while(r - l > 1) {
            int mid = (r + l) >> 1;
            ld mm = mid;
            ld ans = 0;
            ld mx = mid / k + (mid % k > 0);
            ans = (mx * (mx - 1) / 2.);
            if(mid % k != 0) ans += mx * (mid % k) / q;
            else ans += mx;
            if(abs(ans - p / q) < EPS) {
                l = mid;
            }
            else if(ans > p / q) {
                r = mid;
            }
            else {
                l = mid;
            }
        }
        cout << l << '\n';
    }
    return 0;
}