use bigint;
$n=<>;
for(1..$n){
	$_=<>;
	chomp;
	$l=length;
	$s=0;
	$t=0;
	$i=1;
	$m=1;
	for(/./g){
		$t|=$_;
		$s=($s+$_*$m)%9;
		$m=$m*($l-$i)/$i;
		++$i;
	}
	$s=9 if $s==0&&$t;
	print$s,$/;
}