#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <queue>
#include <deque>
#include <numeric>

#define ll              long long 
#define all(v)          v.begin(),v.end()
#define ld              long double
#define pll             std::pair<ll,ll>
#define pi              std::pair<int,int>
#define vi              std::vector<int>
#define vll             std::vector<ll>
#define len(x)          (int)x.size()
#define vec(T)          std::vector<T>
#define PI              (ld)3.14159265358979323846

// overload << for pair
template <typename T>
std::ostream& operator<<(std::ostream& os, const std::pair<T, T>& pair) {
    std::cout << "(" << pair.first << ", " << pair.second << ")";
    return os;
}


// overload << for vec
template <typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& vec) {
    os << "[";
    for (size_t i = 0; i < vec.size(); ++i) {
        os << vec[i] << (i == vec.size() - 1 ? "\0" : ", ");
    }
    os << "]";
    return os;
}


// overload << for map and unordered_map Output
template<typename Map>
void printMap(const Map& m) {
    std::cout << '{';
    for (auto it = m.begin(); it != m.end(); it++) {
        std::cout << it -> first << ": " << it -> second << (std::next(it) == m.end() ? "\0" : ", ");
    }
    std::cout << "}";
}
template <typename K, typename V>
std::ostream& operator<<(std::ostream& os, const std::map<K, V>& m) {
    printMap(m);
    return os;
}
template <typename K, typename V>
std::ostream& operator<<(std::ostream& os, const std::unordered_map<K, V>& m) {
    printMap(m);
    return os;
}

// overload << for set and unordered_set Output
template<typename Set>
void printSet(const Set& s) {
    std::cout << '{';
    for (auto it = s.begin(); it != s.end(); it++) {
        std::cout << *it << (std::next(it) == s.end() ? "\0" : ", ");
    }
    std::cout << "}";
}
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::set<T>& s) {
    printSet(s);
    return os;
}
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::unordered_set<T>& s) {
    printSet(s);
    return os;
}

// General print function
template <typename T>
void print(const T& val) {
    std::cout << val << std::endl;
}

// Variadic template print function
template<typename T, typename... Args>
void print(const T& t, const Args&... args) {
    std::cout << t << ' ';
    print(args...);
    if (sizeof...(args) == 1) std::cout << '\n';

}


void solve(){  
    ll n, m;
    std::cin >> n >> m;
    ll x = m - 1;
    auto f = [&](ll t) {
        ll l = t, r = n;
        while (l < r) {
            ll mid = (l + r) / 2;
            if (mid - mid / m - 1 >= x) {
                r  = mid;
            }
            else {
                l = mid + 1;
            }
        }
        return l;
    };
    if (n <= m) {
        print(n);
        return;
    }
    while (true) {
        ll tmp = f(x);
        if (tmp >= n) break;
        x = tmp;
    }
    print(x + 1);
}
 



    
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t = 1;
    std::cin >> t;
    while (t--) solve();
}