Problem: Following FIFA World Cup, a larger competition called ``GIGA Universe Cup'' is taking place somewhere in our universe. Both FIFA World Cup and GIGA Universe Cup are two rounds competitions that consist of the first round, also known as ``group league,'' and the second called ``final tournament.'' In the first round, participating teams are divided into groups of four teams each. Each team in a group plays a match against each of the other teams in the same group. For example, let's say we have a group of the following four teams, ``Engband, Swedon, Argontina, and Nigerua.'' They play the following six matches: Engband - Swedon, Engband - Argontina, Engband - Nigerua, Swedon - Argontina, Swedon - Nigerua, and Argontina - Nigerua.

The result of a single match is shown by the number of goals scored by each team, like ``Engband 1 - 0 Argontina,'' which says Engband scored one goal whereas Argontina zero. Based on the result of a match, points are given to the two teams as follows and used to rank teams. If a team wins a match (i.e., scores more goals than the other), three points are given to it and zero to the other. If a match draws (i.e., the two teams score the same number of goals), one point is given to each.

The goal difference of a team in given matches is the total number of goals it scored minus the total number of goals its opponents scored in these matches. For example, if we have three matches ``Swedon 1 - 2 Engband,'' ``Swedon 3 - 4 Nigerua,'' and ``Swedon 5 - 6 Argontina,'' then the goal difference of Swedon in these three matches is (1 + 3 + 5) - (2 + 4+ 6) = -3.

Given the results of all the six matches in a group, teams are ranked by the following criteria, listed in the order of priority (that is, we first apply (a) to determine the ranking, with ties broken by (b), with ties broken by (c), and so on).

(a) greater number of points in all the group matches;

(b) greater goal difference in all the group matches;

(c) greater number of goals scored in all the group matches.

If two or more teams are equal on the basis of the above three criteria, their place shall be determined by the following criteria, applied in this order:

(d) greater number of points obtained in the group matches between the teams concerned;

(e) greater goal difference resulting from the group matches between the teams concerned;

(f) greater number of goals scored in the group matches between the teams concerned;

If two or more teams are stiIl equal, apply (d), (e), and (f) as necessary to each such group. Repeat this until those three rules to equal teams do not make any further resolution. Finally, teams that still remain equal are ordered by:

(g) drawing lots by the Organizing Committee for the GIGA Universe Cup.

The two teams coming first and second in each group qualify for the second round.

Your job is to write a program which, given the results of matches played so far in a group and one team specified in the group, calculates the probability that the specified team will qualify for the second round. You may assume each team has played exactly two matches and has one match to play. In total, four matches have been played and two matches are to be played.

Assume the probability that any team scores (exactly) p goals in any match is:

<image>

for p ≤ 8, and zero for p > 8 . Assume the lot in the step (g) is fair.



Input

The first line of the input is an integer, less than 1000, that indicates the number of subsequent records.

The rest of the input is the indicated number of records. A single record has the following format:

<image>

In the above, <_> is a single underscore (_) and <empty> a sequence of exactly four underscores (____). Each of <team>1, ... , <team>4 is either an asterisk character (*) followed by exactly three uppercase letters (e.g., *ENG), or an underscore followed by exactly three uppercase letters (e.g., _SWE). The former indicates that it is the team you are asked to calculate the probability of the second round qualification for. You may assume exactly one of <team>1, ... , <team>4 is marked with an asterisk. Each <m>ij(1 ≤ i < j ≤ 4) is a match result between the <team>i and <team>j. Each match result is either __-_ (i.e., two underscores, hyphen, and another underscore) or of the form _x-y where each of x and y is a single digit (≤ 8) . The former indicates that the corresponding match has not been played, whereas the latter that the result of the match was x goals by <team>i and y goals by <team>j. Since each team has played exactly two matches, exactly two match results are in the former format.

Output

The output should consist of n lines where n is the number of records in the input. The ith line should show the probability that the designated team (marked with an asterisk) will qualify for the second round in the ith record.

Numbers should be printed with exactly seven digits after the decimal point. Each number should not contain an error greater than 10-7.

Example

Input

5
_____*AAA__BBB__CCC__DDD
*AAA_______0-0__0-0___-_
_BBB_____________-___0-0
_CCC_________________0-0
_DDD____________________
______CHN__CRC__TUR_*BRA
_CHN_______0-2___-___0-4
_CRC____________1-1___-_
_TUR_________________1-2
*BRA____________________
______CMR_*KSA__GER__IRL
_CMR_______1-0___-___1-1
*KSA____________0-8___-_
_GER_________________1-1
_IRL____________________
______TUN__JPN_*BEL__RUS
_TUN________-___1-1__0-2
_JPN____________2-2__1-0
*BEL__________________-_
_RUS____________________
______MEX__CRO_*ECU__ITA
_MEX_______1-0__2-1___-_
_CRO_____________-___2-1
*ECU_________________0-2
_ITA____________________


Output

0.5000000
1.0000000
0.0000000
0.3852746
0.0353304

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 4

struct Info{
	bool operator<(const struct Info& arg) const{

		if(points != arg.points){

			return points > arg.points;

		}else if(goal_diff != arg.goal_diff){

			return goal_diff > arg.goal_diff;
		}else{
			return sum_goal > arg.sum_goal;
		}
	}
	bool operator==(const struct Info &arg) const{
		return points == arg.points && goal_diff == arg.goal_diff && sum_goal == arg.sum_goal;
	}

	int team_id,points,goal_diff,sum_goal;
};

struct Data{
	int from_team,to_team;
};

struct State{
	State(int arg_team_id,int arg_rank){

		team_id = arg_team_id;
		rank = arg_rank;
	}
	int team_id,rank;
};

int num_case;
char table[5][25];
double poss_point[9];
Info info[5];
Data data[2];


int get_point(char buf[3]){

	int from_point = buf[0]-'0';
	int to_point = buf[2]-'0';

	if(from_point > to_point){

		return 3;

	}else if(from_point == to_point){

		return 1;

	}else{

		return 0;
	}
}

int get_diff(char buf[3]){

	int from_point = buf[0]-'0';
	int to_point = buf[2]-'0';

	return from_point-to_point;
}

void init(vector<int> member){

	for(int i = 0; i < member.size(); i++){
		info[member[i]].points = 0;
		info[member[i]].goal_diff = 0;
		info[member[i]].sum_goal = 0;
	}
}

//最大2位以内を返す関数(1位が2チーム以上あったら、即返却)
vector<State> select(vector<int> member){

	Info tmp_info[5];
	for(int i = 0; i < member.size(); i++){

		tmp_info[member[i]].points = 0;
		tmp_info[member[i]].goal_diff = 0;
		tmp_info[member[i]].sum_goal = 0;
		tmp_info[member[i]].team_id = member[i];
	}

	int tmp_row,tmp_col,tmp;
	char calc_buf[3];

	for(int i = 0; i < member.size()-1; i++){
		for(int k = i+1; k < member.size(); k++){

			tmp_row = member[i];
			tmp_col = 4+5*(member[k]-1);

			for(int a = 2; a <= 4; a++){
				calc_buf[a-2] = table[tmp_row][tmp_col+a];
			}

			tmp = get_point(calc_buf);

			if(tmp == 1){

				tmp_info[member[i]].points += 1;
				tmp_info[member[k]].points += 1;

			}else{

				tmp_info[member[i]].points += tmp;
				tmp_info[member[k]].points += 3-tmp;
			}

			tmp = get_diff(calc_buf);

			tmp_info[member[i]].goal_diff += tmp;
			tmp_info[member[k]].goal_diff -= tmp;

			tmp_info[member[i]].sum_goal += calc_buf[0]-'0';
			tmp_info[member[k]].sum_goal += calc_buf[2]-'0';
		}
	}

	vector<State> ret;
	vector<Info> calc_info;

	int num = (int)member.size();
	//printf("num:%d\n",num);

	for(int i = 0; i < num; i++){
		calc_info.push_back(tmp_info[member[i]]);
	}

	sort(calc_info.begin(),calc_info.end());

	int base_index = 0,rank = 0,right;

	while(ret.size() < 2 && rank < 2 && base_index < num){

		ret.push_back(State(calc_info[base_index].team_id,rank));

		right = base_index+1;
		if(right == num)break;

		if(calc_info[base_index] == calc_info[right]){

			while(right < num && calc_info[base_index] == calc_info[right]){
				ret.push_back(State(calc_info[right].team_id,rank));
				right++;
			}
			base_index = right;

		}else{

			base_index = right;
		}
		rank++;
	}

	return ret;
}

void func(){

	int base_team,work_index,data_index = 0;

	char work[3];
	vector<int> member;

	for(int i = 1; i <= 4; i++){
		member.push_back(i);
		info[i].team_id = i;
	}

	init(member);

	int from_team,to_team,tmp;

	for(int row = 0; row <= NUM; row++){
		scanf("%s",table[row]);
		if(table[row][0] == '*'){
			base_team = row;
		}

		if(row == 0)continue;

		from_team = row;
		to_team = from_team+1;

		for(int start_col = 4+5*row; start_col <= 19; start_col += 5,to_team++){

			if(table[row][start_col+2] == '_'){ //★結果不明な組合せ★

				data[data_index].from_team = from_team;
				data[data_index++].to_team = to_team;

				continue;
			}

			work_index = 0;
			for(int i = 2; i <= 4; i++){
				work[work_index++] = table[row][start_col+i];
			}

			//勝ち点
			tmp = get_point(work);

			if(tmp == 1){

				info[from_team].points += 1;
				info[to_team].points += 1;

			}else{

				info[from_team].points += tmp;
				info[to_team].points += 3-tmp;
			}

			//goal_diff
			tmp = get_diff(work);
			info[from_team].goal_diff += tmp;
			info[to_team].goal_diff -= tmp;

			//goal総数
			info[from_team].sum_goal += work[0]-'0';
			info[to_team].sum_goal += work[2]-'0';
		}
	}

	double ans = 0;
	double tmp_poss;

	vector<State> Top_Group;

	int tmp_from,tmp_to;
	int pre_size,num_decided,tmp_index,num_rank_0;

	bool check[5];
	bool FLG;

	//未判明の、2試合の得点を全探索
	for(int from_1 = 0; from_1 <= 8;from_1++){
		for(int to_1 = 0; to_1 <= 8; to_1++){
			for(int from_2 = 0; from_2 <= 8; from_2++){
				for(int to_2 = 0; to_2 <= 8; to_2++){

					Top_Group.clear();
					tmp_poss = 1.0;

					//まず、このトーナメント表が出来上がる確率を求める
					tmp_poss *= poss_point[from_1];
					tmp_poss *= poss_point[to_1];
					tmp_poss *= poss_point[from_2];
					tmp_poss *= poss_point[to_2];

					member.clear();
					for(int i = 1; i <= 4; i++){
						member.push_back(i);
					}

					//★表を完成させる★

					for(int loop = 0; loop < 2; loop++){

						from_team = data[loop].from_team;
						to_team = data[loop].to_team;

						if(loop == 0){

							tmp_from = from_1;
							tmp_to = to_1;

						}else{

							tmp_from = from_2;
							tmp_to = to_2;
						}

						//★テーブルを埋める★
						table[from_team][4+5*(to_team-1)+2] = '0'+tmp_from;
						table[from_team][4+5*(to_team-1)+3] = '-';
						table[from_team][4+5*(to_team-1)+4] = '0'+tmp_to;
					}

					num_decided = 0;
					//上位チームを選んでみる(1回目)
					Top_Group = select(member);

					FLG = false;

					num_rank_0 = 0;
					for(int k = 0; k < Top_Group.size(); k++){

						if(Top_Group[k].rank == 0)num_rank_0++;

						if(base_team == Top_Group[k].team_id){
							tmp_index = k;
							FLG = true;
						}
					}

					if(Top_Group.size() == 2){

						//上位2チームに入っていればOK、そうでなければ不可
						if(FLG){
							ans += tmp_poss;
						}else{
							//Do nothing
						}
						continue;

					}else if(Top_Group.size() == 3){

						//★★上位3チームに含まれていなければ不可★★
						if(!FLG)continue;

						//★単独1位ならOK★
						if(Top_Group[tmp_index].rank == 0 && num_rank_0 == 1){
							ans += tmp_poss;
							continue;
						}

					}else{ //Top_Group.size() == 4

						//★単独1位ならOK★
						if(Top_Group[tmp_index].rank == 0 && num_rank_0 == 1){
							ans += tmp_poss;
							continue;
						}
					}

					//通過or脱落が確定した人物を取り除く
					if(num_rank_0 == (int)Top_Group.size()){ //1位が3個か4個

						if(num_rank_0 == 3){ //1人脱落

							for(int k = 1; k <= 4; k++)check[k] = false;

							for(int i = 0; i < Top_Group.size(); i++){
								check[Top_Group[i].team_id] = true;
							}
							member.clear();

							for(int k = 1; k <= 4; k++){
								if(check[k]){
									member.push_back(k);
								}
							}

						}else{ //1位が4人
							//Do nothing
						}

					}else if(num_rank_0 != (int)Top_Group.size()){ //num_rank_0が2以上なら、1ターン目で返る==Top_Groupのサイズと一致する。よって、num_rank_0 == 1

							for(int k = 1; k <= 4; k++)check[k] = false;

							for(int i = 0; i < Top_Group.size(); i++){
								check[Top_Group[i].team_id] = true;
							}
							member.clear();

							for(int k = 0; k < Top_Group.size(); k++){
								if(Top_Group[k].rank != 0)continue;

								num_decided++;
								check[Top_Group[k].team_id] = false; //通過が確定したので集合から除く
							}

							for(int k = 1; k <= 4; k++){
								if(check[k]){
									member.push_back(k);
								}
							}
					}

					int debug = (int)member.size();
					pre_size = (int)member.size();

					//★★2位通過が決定するまで、ループ★★
					while(true){

						Top_Group = select(member);

						FLG = false;
						num_rank_0 = 0;
						for(int k = 0; k < Top_Group.size(); k++){

							if(Top_Group[k].rank == 0)num_rank_0++;

							if(base_team == Top_Group[k].team_id){
								tmp_index = k;
								FLG = true;
							}
						}

						if(num_decided+(int)Top_Group.size() == 2){ //上位2チーム決定

							if(FLG){ //上位2チームに含まれれば良い

								ans += tmp_poss;

							}else{
								//Do nothing
							}

							break;

						}else if(num_decided+num_rank_0 == 2){ //1位のチームのみ抜き出せば、上位2チーム決定

							if(FLG == true && Top_Group[tmp_index].rank == 0){ //1位

								ans += tmp_poss;

							}else{ //★他のチームによって枠が取られた場合★

								//Do nothing
							}

							break;
						}


						//通過or脱落が確定した人物を取り除く
						if(num_rank_0 == (int)Top_Group.size()){ //1位が2～4個

							if(num_rank_0 <= 3){ //1人～2人脱落

								for(int k = 1; k <= 4; k++)check[k] = false;

								for(int i = 0; i < Top_Group.size(); i++){
									check[Top_Group[i].team_id] = true;
								}
								member.clear();

								for(int k = 1; k <= 4; k++){
									if(check[k]){
										member.push_back(k);
									}
								}

							}else{ //1位が4人
								//Do nothing
							}

						}else if(num_rank_0 != Top_Group.size()){

								if(FLG == true && Top_Group[tmp_index].rank == 0){ //単独1位
									ans += tmp_poss;
									break;
								}

								for(int k = 1; k <= 4; k++)check[k] = false;

								for(int i = 0; i < member.size(); i++){
									check[member[i]] = true;
								}
								member.clear();

								for(int k = 0; k < Top_Group.size(); k++){
									if(Top_Group[k].rank != 0)continue;

									num_decided++;
									check[Top_Group[k].team_id] = false; //通過が確定したので集合から除く
								}

								for(int k = 1; k <= 4; k++){
									if(check[k]){
										member.push_back(k);
									}
								}
						}


						if((int)member.size() == pre_size){

							if(FLG){

								if(num_decided == 1){ //1つ選ぶ

									ans += tmp_poss/(double)member.size();

								}else{ //★★★2つ選ぶ★★★

									ans += tmp_poss*2.0/(double)member.size();
								}

							}else{

								//Do nothing
							}

							break;
						}

						pre_size = (int)member.size();
					}

				}
			}
		}
	}

	printf("%.10lf\n",ans);

}

void calc_poss(){

	int nCm[9][9];

	for(int i = 0; i <= 8; i++){
		for(int k = 0; k <= 8; k++)nCm[i][k]= 0;
	}

	nCm[0][0] = 1;
	for(int n = 1; n <= 8; n++) {
		for (int k = 0; k <= 8; k++) {
			if(k > 0){
				nCm[n][k] = nCm[n-1][k]+nCm[n-1][k-1];
			}else{ //k == 0
				nCm[n][k] = 1;
			}
		}
	}

	double poss;

	for(int point = 0; point <= 8; point++){

		poss = nCm[8][point];

		for(int i = 0; i < point; i++){
			poss *= 0.25;
		}
		for(int i = 0; i < 8-point; i++){
			poss *= 0.75;
		}
		poss_point[point] = poss;
	}
}

int main(){

	calc_poss();

	scanf("%d",&num_case);

	for(int loop = 0; loop < num_case; loop++){
		func();
	}

	return 0;
}