#include<bits/stdc++.h>

using namespace std;

long long n, k;

int main(){
    int tc;
    cin >> tc;
    for(int i = 0; i < tc; ++i){
    	cin >> n >> k;
    	long long res = 0;
    	while(n > 0){
    	    if(n % k == 0){
    	        n /= k;
    	        ++res;
    	    }
    	    else{
    	        long long rem = n % k;
    	        res += rem;
    	        n -= rem;
    	    }
    	}
    	
    	cout << res << endl;
    }
	return 0;
}

#include <bits/stdc++.h>

#define forn(i, n) for(int i = 0; i < int(n); i++) 

using namespace std;

const long long INF = 1ll << 32;

int main(){
	int l;
	cin >> l;
	
	stack<long long> cur;
	cur.push(1);
	
	long long res = 0;
	forn(_, l){
		string t;
		cin >> t;
		if (t == "for"){
			int x;
			cin >> x;
			cur.push(min(INF, cur.top() * x));
		}
		else if (t == "end"){
			cur.pop();
		}
		else{
			res += cur.top();
		}
	}
	
	if (res >= INF)
		cout << "OVERFLOW!!!" << endl;
	else
		cout << res << endl;
}

#include<bits/stdc++.h>

using namespace std;

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())

int n, k;
vector<int> a;

inline bool read() {
	if(!(cin >> n >> k))
		return false;
	a.resize(n);
	fore(i, 0, n)
		cin >> a[i];
	return true;
}

inline void solve() {
	pair<int, int> ans = {int(1e9) + 7, -1};
	fore(i, 0, n - k) {
		int dist = a[i + k] - a[i];
		ans = min(ans, make_pair(dist, a[i] + dist / 2));
	}
	
	cout << ans.second << endl;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	int tt = clock();
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cout << fixed << setprecision(15);
	
	int tc; cin >> tc;
	
	while(tc--) {
	    read();
		solve();
		
#ifdef _DEBUG
		cerr << "TIME = " << clock() - tt << endl;
		tt = clock();
#endif
	}
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

const int N = 300009;

int n, k;
int a[N];

int main(){
	cin >> n >> k;
	for(int i = 0; i < n; ++i)
		cin >> a[i];
	
	long long sum = 0;
	vector <long long> v;
	for(int i = n - 1; i >= 0; --i){
	    sum += a[i];
	    if(i > 0) v.push_back(sum);
	}
	
	long long res = sum;
	
	sort(v.begin(), v.end());
	reverse(v.begin(), v.end());
	
	
	for(int i = 0; i < k - 1; ++i)
	    res += v[i];
	    
	cout << res << endl;
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second
#define forn(i, n) for(int i = 0; i < int(n); i++) 

const int N = 500 * 1000 + 13;
const int LOGN = 18;

int n, m;
pair<int, int> a[N], q[N];

int nxt[N];
int up[LOGN][N];

int main(){
	scanf("%d%d", &n, &m);
	forn(i, n)
		scanf("%d%d", &a[i].x, &a[i].y);
	forn(i, m)
		scanf("%d%d", &q[i].x, &q[i].y);
	
	sort(a, a + n);
	
	int lst = 0;
	pair<int, int> mx(0, -1);
	forn(i, N){
		while (lst < n && a[lst].x == i){
			mx = max(mx, make_pair(a[lst].y, lst));
			++lst;
		}
		nxt[i] = (mx.x <= i ? -1 : mx.y);
	}
	
	forn(i, n)
		up[0][i] = nxt[a[i].y];
	for (int j = 1; j < LOGN; ++j) forn(i, n){
		if (up[j - 1][i] == -1)
			up[j][i] = -1;
		else
			up[j][i] = up[j - 1][up[j - 1][i]];
	}
	
	forn(i, m){
		int x = nxt[q[i].x];
		
		if (x == -1){
			puts("-1");
			continue;
		}
		
		int res = 1;
		for (int j = LOGN - 1; j >= 0; --j){
			int y = up[j][x];
			if (y == -1)
				continue;
			if (a[y].y < q[i].y){
				res += (1 << j);
				x = y;
			}
		}
		
		if (a[x].y >= q[i].y)
			printf("%d\n", res);
		else if (up[0][x] == -1)
			puts("-1");
		else
			printf("%d\n", res + 1);
	}
}

#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second
#define forn(i, n) for(int i = 0; i < int(n); i++) 

const int N = 500 * 1000 + 13;

int n, m;
pair<int, int> a[N], q[N];

int nxt[N];
int ans[N];

pair<int, int> p[N];

pair<int, int> get(int x, int r){
	if (x == -1)
		return make_pair(-1, -1);
	if (a[x].y >= r)
		return make_pair(x, 0);
	auto res = get(p[x].x, r);
	if (res.x == -1)
		p[x] = make_pair(-1, -1);
	else
		p[x] = make_pair(res.x, p[x].y + res.y);
	return p[x];
}

int main(){
	scanf("%d%d", &n, &m);
	forn(i, n)
		scanf("%d%d", &a[i].x, &a[i].y);
	forn(i, m)
		scanf("%d%d", &q[i].x, &q[i].y);
	sort(a, a + n);
	
	int lst = 0;
	pair<int, int> mx(0, -1);
	forn(i, N){
		while (lst < n && a[lst].x == i){
			mx = max(mx, make_pair(a[lst].y, lst));
			++lst;
		}
		nxt[i] = (mx.x <= i ? -1 : mx.y);
	}
	
	vector<int> perm(m);
	iota(perm.begin(), perm.end(), 0);
	sort(perm.begin(), perm.end(), [](int a, int b){
		return q[a].y < q[b].y;
	});
	
	forn(i, n)
		p[i] = make_pair(nxt[a[i].y], nxt[a[i].y] == -1 ? -1 : 1);
	
	for (auto i : perm){
		int x = nxt[q[i].x];
		auto res = get(x, q[i].y).y;
		ans[i] = (res == -1 ? -1 : res + 1);
	}
	
	forn(i, m)
		printf("%d\n", ans[i]);
}

#include <bits/stdc++.h>

using namespace std;

typedef pair<long long, long long> pt;

const int N = int(3e5) + 99;
const pt zero = make_pair(0, 0);

int n;
int a[N];
pt hsh[N], sumHsh[N];
pt prefsum[N];

void upd(pt &a, pt b){
    a.first ^= b.first;
    a.second ^= b.second;
}

pt f(int l, int r){
	pt res = prefsum[r];
	if(l > 0) upd(res, prefsum[l - 1]);
	return res;
}

int calc(int pos){
    int r = pos, len = 0, res = 0;
	while(r < n - 1 && a[r + 1] != 0){
		len = max(len, a[r + 1] + 1);
		++r;
		if(r - len + 1 >= 0 && f(r - len + 1, r) == sumHsh[len - 1])
			++res;
	}
	
	return res;
}	

int main() {
	long long x = 0;
	cin >> n;
	for(int i = 0; i < n; ++i){
		cin >> a[i];
		--a[i];	
		x ^= a[i];
	}
	
	
	mt19937 rnd(time(NULL));
	for(int i = 0; i < N; ++i){
		hsh[i].first = rnd() ^ x;
		hsh[i].second = rnd() ^ x;
		sumHsh[i] = hsh[i];
		if(i > 0) upd(sumHsh[i], sumHsh[i - 1]);
	}
	
	int res = 0;
		
	for(int tc = 0; tc < 2; ++tc){
		for(int i = 0; i < n; ++i){
			prefsum[i] = hsh[a[i]];
			if(i > 0) upd(prefsum[i], prefsum[i - 1]);
		}
		for(int i = 0; i < n; ++i)
			if(a[i] == 0)
				res += calc(i) + (tc == 0);
		reverse(a, a + n);
	}
	cout << res << endl;

	return 0;
} 

#include<bits/stdc++.h>

using namespace std;

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) (int)((a).size())

#define x first
#define y second

typedef long long li;
typedef pair<li, li> pt;

const int INF = int(1e9);
const li INF64 = li(1e9);

pt operator -(const pt &a, const pt &b) {
    return {a.x - b.x, a.y - b.y};
}
li operator *(const pt &a, const pt &b) {
    return a.x * b.x + a.y * b.y;
}
li operator %(const pt &a, const pt &b) {
    return a.x * b.y - a.y * b.x;
}
pt rotate(const pt &p) {
    return {-p.y, p.x};
}

struct LinearHull {
    deque<pt> pts, vecs;

    void addRight(const pt &l) {
        while(!vecs.empty() && vecs.back() * (l - pts.back()) < 0) {
            vecs.pop_back();
            pts.pop_back();
        }
        if(!pts.empty())
            vecs.push_back(rotate(l - pts.back()));
        pts.push_back(l);
    }
    void addLeft(const pt &l) {
        while(!vecs.empty() && vecs.front() * (l - pts.front()) < 0) {
            vecs.pop_front();
            pts.pop_front();
        }
        if(!pts.empty())
            vecs.push_front(rotate(pts.front() - l));
        pts.push_front(l);
    }

    li getMin(const pt &x) {
        auto it = lower_bound(vecs.begin(), vecs.end(), x, [](const pt &a, const pt &b) {
            return a % b > 0;
        });
        return x * pts[it - vecs.begin()];
    }
};

typedef unique_ptr<LinearHull> pHull;

void mergeHulls(pHull &a, pHull &b) {
    if(sz(b->pts) >= sz(a->pts)) {
        for(auto &p : a->pts)
            b->addRight(p);
    } else {
        for(auto it = b->pts.rbegin(); it != b->pts.rend(); it++)
            a->addLeft(*it);
        swap(a, b);
    }
}

const int M = 1000 * 1000 + 555;
int szn = 0;
struct node {
    pt line;
    node *l, *r;

    node() : line(), l(nullptr), r(nullptr) {}
    node(pt line, node *l, node *r) : line(move(line)), l(l), r(r) {}
} nodes[M];

typedef node* tree;

tree getNode(const pt &line, tree l, tree r) {
    assert(szn < M);
    nodes[szn] = node(line, l, r);
    return &nodes[szn++];
}
tree copy(tree v) {
    if(v == nullptr) return v;
    return getNode(v->line, v->l, v->r);
}

li f(const pt &line, int x) {
    return line * pt{x, 1};
}

tree addLine(tree v, int l, int r, pt line) {
    if(!v)
        return getNode(line, nullptr, nullptr);
    int mid = (l + r) >> 1;
    bool lf = f(line, l) < f(v->line, l);
    bool md = f(line, mid) < f(v->line, mid);

    if(md)
        swap(v->line, line);

    if(l + 1 == r)
        return v;
    else if(lf != md)
        v->l = addLine(copy(v->l), l, mid, line);
    else
        v->r = addLine(copy(v->r), mid, r, line);
    return v;
}

li getMin(tree v, int l, int r, int x) {
    if(!v) return INF64;
    if(l + 1 == r)
        return f(v->line, x);
    int mid = (l + r) >> 1;

    if(x < mid)
        return min(f(v->line, x), getMin(v->l, l, mid, x));
    else
        return min(f(v->line, x), getMin(v->r, mid, r, x));
}

int n, k;
vector<li> a;

inline bool read() {
    if(!(cin >> n >> k))
        return false;
    a.resize(n);

    fore(i, 0, n)
        cin >> a[i];
    return true;
}

struct state {
    int pos;
    pHull hull;
    tree v;

    state() : pos(-1), hull(nullptr), v(nullptr) {}
};

vector<li> d[2];

inline void solve() {
    int maxn = (int)*max_element(a.begin(), a.end()) + 3;
    fore(k, 0, 2)
        d[k].resize(n + 1, INF64);

    d[0][0] = 0;
    fore(_k, 1, k + 1) {
        szn = 0;

        int ck = _k & 1;
        int nk = ck ^ 1;

        vector< state > st;

        fore(i, 0, sz(d[ck])) {
            d[ck][i] = INF64;
            if(!st.empty())
                d[ck][i] = getMin(st.back().v, 0, maxn, i);

            if(i >= sz(a))
                continue;

            state curVal;
            curVal.pos = i;
            curVal.hull = make_unique<LinearHull>();
            curVal.hull->addRight({-i, d[nk][i]});
            curVal.v = nullptr;

            while(!st.empty() && a[st.back().pos] < a[i]) {
                mergeHulls(st.back().hull, curVal.hull);
                st.pop_back();
            }
            if(!st.empty())
                curVal.v = st.back().v;

            li val = curVal.hull->getMin({a[i], 1});
            curVal.v = addLine(copy(curVal.v), 0, maxn, {a[i], val});

            st.push_back(move(curVal));
        }
    }
    cout << d[k & 1][n] << endl;
}

int main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    int tt = clock();
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cout << fixed << setprecision(15);

    if(read()) {
        solve();

#ifdef _DEBUG
        cerr << "TIME = " << clock() - tt << endl;
        tt = clock();
#endif
    }
    return 0;
}