#include <stdio.h>
#include <limits.h>
#include <unordered_map>
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;

unordered_map<int, int> m;

int ans(int n){
	if(n <= 2) return n;
	if(m.count(n)) return m[n];
	m[n] = min(ans(n/2)+n%2, ans(n/3)+n%3)+1;
	return m[n];
}

int main(){
	int t, n;
	scanf("%d", &t);
	while(t--){
		scanf("%d", &n);
		printf("%d\n", ans(n));
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;

int b[100010];
typedef pair<int,int> T;
int ans(vector<vector<int> > &a, int p, int k){
	priority_queue<T, vector<T>, greater<T> > q;
	vector<int> index(p, 1);
	for(int i = 0; i < p; i++){
		q.push(make_pair(a[b[i]][0], i));
	}
	int cnt = 1;
	while(cnt < k){
		int i = q.top().second;
		q.pop();
		if(index[i] < a[b[i]].size()) {
			q.push(make_pair(a[b[i]][index[i]], i));
			index[i]++;
		}
		cnt++;
	}
	return q.top().first;
}

int main(){
	int n, m, q, p, k;
	scanf("%d", &n);
	vector<vector<int> > a(n+1);
	for(int i = 1; i <= n; ++i){
		scanf("%d", &m);
		a[i].resize(m);
		for(int j = 0; j < m; ++j)
			scanf("%d", &a[i][j]);
		sort(a[i].begin(), a[i].end());
	}
	scanf("%d", &q);
	while(q--){
		scanf("%d", &p);
		for(int i = 0; i < p; ++i){
			scanf("%d", &b[i]);
		}
		scanf("%d", &k);
		printf("%d\n", ans(a, p, k));
	}
	return 0;
}

#include <stdio.h>
#include <algorithm>
using namespace std;
#define max(a,b) ((a)>(b)?(a):(b))
struct node{
    int x, y;
};

bool cmp(const node &a, const node &b){
    return a.x < b.x;
}

node a[100010];
int check(long long w, int n, int x){
    long long sum = 0;
    int cntl = 0, cntr = 0;
    for(int i = 0; i < n; ++i){
        if(a[i].y < x) {
            sum += a[i].x;
            cntl++;
        }
        else if(a[i].x > x) {
            sum += a[i].x;
            cntr++;
        }
    }
    int t = n / 2;
    if(cntl > t) return 1;//too high
    if(cntr > t) return -1; //too low
    for(int i = 0; i < n && cntl < t; i++){
        if(a[i].x <= x && x <= a[i].y){
            sum += a[i].x;
            cntl++;
        }
    }
    if(sum + (t-cntr)*x + x <= w) return 0;
    return 1; //too high
}

int main(){
    int n;
    long long w;
    scanf("%d%lld", &n, &w);
    for(int i = 0; i < n; ++i) scanf("%d%d", &a[i].x, &a[i].y);
    sort(a, a+n, cmp);
    long long sum = 0;
    int l = 0, r = 1e9, ans = 0;
    while(l <= r){
        int mid = (l+r)/2, res = check(w, n, mid);
        if(res == 0){
            ans = mid;
            l = mid+1;
        }
        else if(res == 1) r = mid-1;
        else l = mid+1;
    }
    printf("%d\n", ans);
    return 0;
}

#include <stdio.h>
#include <string.h>
#define N 100010
#define min(a,b) ((a)<(b)?(a):(b))
int w[N];
long long dp[101];
bool v[101];
int main(){
	int t, n, m;
	scanf("%d", &t);
	while(t--){
		scanf("%d%d", &n, &m);
		memset(dp, -1, sizeof(dp));
		long long sum = 0;
		dp[0] = 0;
		for(int i = 0; i < n; ++i) {
			scanf("%d", &w[i]);
			long long dp2[101]; //可以用滚动数组 
			for(int i = 0; i < m; ++i) dp2[i] = dp[i];
			for(int j = 0; j < m; ++j){
				if(dp[j] == -1) continue;
				if(dp2[(j+w[i])%m] == -1 || dp2[(j+w[i])%m] < dp[j] + w[i]) {
					dp2[(j+w[i])%m] = dp[j] + w[i];
				}
			}
			for(int i = 0; i < m; ++i) dp[i] = dp2[i];
			sum += w[i];
		}
		printf("%lld\n", sum-dp[0]);
	}
	return 0;
}