#include <bits/stdc++.h>
#define N (200000 + 10)  /*------------------ #define ------------------*/
#define M (400000 + 10)
#define MOD (1000000000 + 7)
//#define MOD (998244353)
#define INF (0x3f3f3f3f)
#define LNF (3e18)
#define mod(a,b) (((a)%(b)+(b))%(b))
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<int,LL> PIL;
typedef pair<LL,int> PLI;
typedef pair<double,double> PDD;

int n;
LL a[N];

LL carry = 0;

LL add(LL x,LL y){
	LL z = 0,p = 0,c = 0;
	while(x || y){
		LL x0 = x % 10,y0 = y % 10;
		if(x0 + y0 + c >= 10){
			carry ++ ;
			z += pow(10,p) * (x0 + y0 + c - 10);
			c = 1;
		}else{
			c = 0;
			z += pow(10,p) * (x0 + y0 + c);
		}
		x /= 10,y /= 10,p ++ ;
	}
	if(c){
		z += pow(10,p) * c;
	}
	return z;
}

LL calc(){
	carry = 0;
	LL z = 0;
	for(int i = 1;i <= n;i ++ ) z = add(z,a[i]);
	return carry;
}

LL ac_ans = 2e9;

int m;
vector<int> path;
void dfs(int u,int state){
	if(u == m + 1){
		carry = 0;
		LL z = 0;
		for(int v : path){
			z = add(z,a[v]);
		}
		ac_ans = min(ac_ans,carry);
		return;
	}
	for(int i = 1;i <= m;i ++ )
		if(!(state >> i & 1)){
			path.push_back(i);
			dfs(u + 1,state | (1 << i));
			path.pop_back();
		}
}

auto solve(){
	
	cin >> n;
	m = n;
	for(int i = 1;i <= n;i ++ ) cin >> a[i];
	
	// dfs(1,0);
	
	sort(a + 1,a + 1 + n);
	int ans1 = calc();
	
	sort(a + 1,a + 1 + n,greater<int>());
	int ans2 = calc();
	
	cout << min(ans1,ans2) << '\n';
	
	// if(min(ans1,ans2) == ac_ans){
		// cout << "Accept\n";
	// }else{
		// cout << "WA\n";
	// }
	
}

signed main(){
	IOS
	int T = 1;
	//
	cin >> T;
	while(T -- ) solve();
	//while(T -- ) cout << (solve() ? "YES" : "NO") << '\n';

    return 0;
}