Четвёртый открытый Зеленоградский турнир 2008

import java.io.*;
import java.util.*;

public class Main implements Runnable
{
	
	final private boolean DEBUG = false;
	
	final private double small = 0.0396; 
	
	class point
	{
		double x, y;
		point(double X, double Y)
		{
			x = X; y = Y;
		}
	}
	
	class compareY implements Comparator<point>{

		public int compare(point a, point b) {
			if(a.y == b.y)return (int)(a.x - b.x);
			return (a.y < b.y)?-1:1;
		}		
	}
	
	class compareX implements Comparator<point>{

		public int compare(point a, point b) {
			if(a.x == b.x)return (int)(a.y - b.y);
			return (a.x < b.x)?-1:1;
		}		
	}
	
	int all = 0;
	
	ArrayList<point> c;
	double xmin, xmax, ymin, ymax;
	double p2 = 0.5000, p3 = 0.3333, p4 = 0.25000, p5 = 0.20000, p6 = 0.1666667;
	double p8 = p4 * 0.5000, p16 = p8 * 0.50000;
	
	PrintWriter cout;
	
	ArrayList<Integer> right;
	
	double EPS = 0.04, Amin = -Math.PI / 3, Amax = Math.PI / 3;

	
	char checkOneLetter(ArrayList<point> a){
		++all;
		 xmin = Collections.min(a, new compareX()).x;
		 xmax= Collections.max(a, new compareX()).x;
		 ymin = Collections.min(a, new compareY()).y;
		 ymax= Collections.max(a, new compareY()).y;
		for(int i = 0; i < a.size();i++){
			point p = a.get(i);
			p.x -= xmin;
			p.y -= ymin;
			p.x /= (xmax - xmin);
			p.y /= (ymax - ymin);
			a.set(i, p);
		}
		if(DEBUG){
			printLetter(a);
		}
		char res = ' ';

		
		double[] p = new double[8];
		p[0] = Math.min(distTo(new point(1, p2), a), distTo(new point(1 - p16, p2), a));
		if(Math.abs(p[0]) < small){
			// part 1
			p[1] = Math.min(Math.min(distTo(new point(p2, p2), a), distTo(new point(p2, p2 + p16), a)), Math.min(distTo(new point(p2 + p16, p2), a), distTo(new point(p2 - p16, p2), a)));
			if (Math.abs(p[1]) < small){
				// part 3
				p[2] = Math.min(distTo(new point(1, 1), a), distTo(new point(1 - p16 / 2, 1 - p16), a));
				if(Math.abs(p[2]) < small){
					// part 7
					p[3] = distTo(new point(3 * p4, p2), a);
					if(Math.abs(p[3]) < small){
						return (checkI(a) < checkM(a))?'I':'M';
					}else{
						p[4] = distTo(new point(p2, p4), a);
						if(Math.abs(p[4]) < small){
							return (checkE(a) < checkB(a))?'E':'B';
						}else{
							return 'Z';
						}
					}
				}else{
					// part 8
					p[3] = Math.min(distTo(new point(0, 1), a), distTo(new point(p16, 1 - p16), a));
					if(Math.abs(p[3]) < small){
						// part 16
						p[4] = distTo(new point(p2, p5), a);
						if(Math.abs(p[4]) < small){
							return (checkF(a) < checkM(a))?'F':'M';
						}else{
							p[5] = distTo(new point(EPS, p2), a);
							if(Math.abs(p[5]) < small){
								p[6] = Math.min(distTo(new point(0, 0), a), distTo(new point(EPS, p16), a));
								if(Math.abs(p[6]) < small){
									return 'T';
								}else{
									p[7] = Math.min(distTo(new point(p8, p8), a), distTo(new point(p8 + EPS, p8 + p16), a));
									return (Math.abs(p[7]) < small)?'G':'J';
								}
							}else{
								return 'Y';
							}
						}
					}else{
						// part 17
						double best = checkI(a);
						res = 'I';
						double s = checkB(a);
						if(s < best){
							best = s;
							res = 'B';
						}
						s = checkE(a);
						if(s < best){
							best = s;
							res = 'E';
						}
						s = checkG(a);
						if(s < best){
							best = s;
							res = 'G';
						}
						s = checkP(a);
						if(s < best){
							best = s;
							res = 'P';
						}
						s = checkS(a);
						if(s < best){
							best = s;
							res = 'S';
						}
					}
				}
			}else
			{
				// part 4
				p[2] = Math.min(distTo(new point(1, 1), a), distTo(new point(1 - 16, 1 - 16), a));
				if(Math.abs(p[2]) < small){
					// part 9
					p[3] = Math.min(distTo(new point(0, 1), a), distTo(new point(EPS, 1 - p16), a));
					if(Math.abs(p[3]) < small){
						// part 18
						return 'M';
					}else{
						// part 19
						p[4] = Math.min(distTo(new point(0, 0), a), distTo(new point(p16, p16), a));
						return (Math.abs(p[4]) < small)?'L':'Q';
					}
				}else{
					// part 10
					p[3] = Math.min(distTo(new point(0, 1), a), distTo(new point(p16, 1 - p16), a));
					if(Math.abs(p[3]) < small){
						// part 20
						p[4] = Math.min(distTo(new point(0, 0), a), distTo(new point(p16, p16), a));
						if(Math.abs(p[4]) < small){
							// UV
							p[5] = distTo(new point(p2, p4), a);
							return (Math.abs(p[5]) < small)?'V':'U';
						}else{
							// CJ
							p[5] = distTo(new point(p2 - Math.sqrt(2.0) / 4.0, p2 - Math.sqrt(2.0) / 4.0), a);
							return (Math.abs(p[5]) < small)?'C':'J';
						}
					}else{
						// part 21
						p[4] = Math.min(distTo(new point(0, 0), a), distTo(new point(EPS, p16), a));
						if(Math.abs(p[4]) < small){
							p[5] = distTo(new point(p2, 1 - p16), a);
							return (Math.abs(p[5]) < small)?'D':'L';
						}else{
							// OCG Qc
							p[5] = distTo(new point(p2, 1 - p8), a);
							if(Math.abs(p[5]) < small){
								// OG Q
								// here should be dfs for filled region by O !!!
								p[6] = distTo(new point(1.0 - p5, p2), a);
								if(Math.abs(p[6]) < small){
									return 'Q';
								}else{
									p[7] = Math.min(distTo(new point(2 * p3, p2), a), distTo(new point(p2, 2 * p3), a));
									return (Math.abs(p[7]) < small)?'G':'O';
								}
							}else{
								return 'C';
							}
						}
					}
				}
			}
		}else{
			// part 2
			p[1] = Math.min(Math.min(distTo(new point(p2, p2), a), distTo(new point(p2 - p16, p2), a)), distTo(new point(p2, p2 - p16), a));
			if (Math.abs(p[1]) < small){
				// part 5
				p[2] = Math.min(distTo(new point(1, 1), a), distTo(new point(1 - p16, 1 - p16), a));
				if(Math.abs(p[2]) < small){
					// part 11
					p[3] = Math.min(distTo(new point(0, 1), a), distTo(new point(EPS, 1 - p16), a));
					if(Math.abs(p[3]) < small){
						// part 22
						p[4] = Math.min(distTo(new point(p2, 0), a), Math.min(distTo(new point(p2, p8), a), distTo(new point(p2, p4), a)));
						if(Math.abs(p[4]) < small){
							// KNH M
							p[5] = Math.min(distTo(new point(p2, 1), a), Math.min(distTo(new point(p2, 1 - p8), a), distTo(new point(p2, 1 - p4), a)));
							if(Math.abs(p[5]) < small){
								p[6] = distTo(new point(p4, p2 + p8), a);
								if(Math.abs(p[6]) < small){
									return 'M';
								}else{
									return (checkH(a) < checkN(a))?'H':'N';
								}
							}else{
								return 'K';
							}
						}else{
							// X
							return 'X';
						}
					}else{
						// part 23
						p[4] = distTo(new point(p16, p2), a);
						return (Math.abs(p[4]) < small)?'R':'K';
					}
				}else{
					// part 12
					p[3] = Math.min(distTo(new point(0, 1), a), distTo(new point(p16, 1 - p16), a));
					if(Math.abs(p[3]) < small){
						// part 24
						p[4] = distTo(new point(p2, 1 - p16), a);
						if(Math.abs(p[4]) >= small){
							// F W
							p[5] = distTo(new point(1 - p16, p16), a);
							return (Math.abs(p[5]) < small)?'F':'W';
						}else{
							p[5] = distTo(new point(3 * p4, 3 * p8), a);
							return (Math.abs(p[5]) < small)?'W':'N';
						}
					}else{
						// part 25
						return 'P';
					}
				}
			}else
			{
				// part 6
				p[2] = Math.min(distTo(new point(1, 1), a), distTo(new point(1 - p16, 1 - p16), a));
				if(Math.abs(p[2]) < small){
					// part 13
					p[3] = Math.min(distTo(new point(0, 1), a), distTo(new point(EPS, 1 - p16), a));
					if(Math.abs(p[3]) < small){
						// part 26
						return 'M';
					}else{
						// part 27
						p[4] = Math.min(distTo(new point(1, 0), a), distTo(new point(1 - EPS, EPS), a));
						return (Math.abs(p[4]) < small)?'A':'Q';
					}
				}else{
					// part 14
					return 'W';
				}
			}
		}
		return res;
	}
	
	
	
	ArrayList<point> trans(ArrayList<point> a, double fi){
		ArrayList<point> res = new ArrayList<point>();
		for (point p: a) {
			res.add(new point(p.x * Math.cos(fi) + p.y * Math.sin(fi), 
					p.y * Math.cos(fi) - p.x * Math.sin(fi)));
		}
		return res;
	}
	
	double fun(double Q)
	{
		ArrayList<point> t = trans(XY, Q);
		double xmax = Collections.max(t, new compareX()).x;
		double xmin = Collections.min(t, new compareX()).x;
		return xmax - xmin;
	}

	double CalcRo()
	{
		double minv = 1E+20;
		double l = Amin, r = Amax;
		double a = l, b = r;
		double coef = 0.8600;
		int iter = 6;
		double minp = l;
		while (Math.abs(r - l) > EPS)
		{
			double c = l;
			double step = (r - l) / iter;
			for (int i = 0; i <= iter; i++)
			{
				double temp = fun(c);
				if (temp < minv)
				{
					minv = temp;
					minp = c;
				}
				c += step;
			}
			double wi = (r - l) * coef / 2.0;
			l = minp - wi;
			r = minp + wi;
			if (l < a)
			{
				l = a;
				r = a + wi * 2.0;
			}
			if (r > b)
			{
				r = b;
				l = b - wi * 2.0;
			}
			coef -= 0.01;
			if (coef < 0.54) coef = 0.54;
		}
		return minp;
	}


	public static void main(String[] args) throws Exception
	{
		Main solve = new Main();
		solve.run();
	}
	
	String[] map;
	
	
	
	void run2()throws Exception
	{
		BufferedReader cin;
		
		StringTokenizer sto = null;
		if(DEBUG){
			cin = new BufferedReader(new FileReader("input.txt"));
			cout = new PrintWriter("output.txt");
		}else{
			cout = new PrintWriter(System.out);
			cin = new BufferedReader(new InputStreamReader(System.in));
		}
		
		
		
		int tests = Integer.parseInt(cin.readLine());
		
		for(int t = 0; t < tests; t++){
			map = new String[200];
			for (int i = 0; i < map.length; i++) {
				if(sto == null || !sto.hasMoreTokens())
				sto = new StringTokenizer(cin.readLine());
				map[i] = sto.nextToken();
			}
			goEating();
		}
		cout.close();
	}

	boolean[][] used;
	ArrayList<point> cur;
	ArrayList<point> xy, XY;
	int  k;
	
	private void goEating() {
		used = new boolean[200][200];
		right = new ArrayList<Integer>();
		xy = new ArrayList<point>();
		XY = new ArrayList<point>();
		for (int j = 0; j < 200; j++){
			for(int i = 0; i < 200; i++){
				if(used[i][j] || map[i].charAt(j) == '.'){
					continue;
				}
				k = 0;
				cur = new ArrayList<point>();
				dfs(i, j);
				if(k < 15){
					continue;
				}
				xy.addAll(cur);
				right.add(xy.size() - 1);
			}
		}
		//
		//cout.println(XY.size());
		double angle = CalcRo();
		//
		if (DEBUG){
			cout.println(angle/Math.PI * 180);
		}
		//
		for(int i = 0; i < xy.size(); i++){
			point p = xy.get(i);
			p = new point(p.x * Math.cos(angle) + p.y * Math.sin(angle), 
					p.y * Math.cos(angle) - p.x * Math.sin(angle));
			xy.set(i, p);
		}
		//
		int st = 0;
		for(int i : right){
			cur = new ArrayList<point>();
			for(int j = st; j <= i; j++){
				cur.add(new point(xy.get(j).x, xy.get(j).y));
			}
			st = i + 1;
			cout.print(checkOneLetter(cur));
		}
		cout.println();
	}

	int[] dx = {0, 0, -1, 1, 1, -1, 1, -1};
	int[] dy = {-1, 1, 0, 0, -1, -1, 1, 1};
	
	private int sosed(int i , int j){
		int res = 0;
		res += (i + 1 < 200 && map[i + 1].charAt(j) == 'X')?1:0;
		res += (j + 1 < 200 && map[i].charAt(j + 1) == 'X')?1:0;
		res += (i - 1 > -1 && map[i - 1].charAt(j) == 'X')?1:0;
		res += (j - 1 > -1 && map[i].charAt(j - 1) == 'X')?1:0;
		return res;
	}
	
	private void dfs(int i, int j) {
		used[i][j] = true;
		++k;
		if(sosed(i, j) >= 2){
			cur.add(new point(i, j));
			if(cur.size() % 12 == 7){
				XY.add(cur.get(cur.size() - 1));
			}
		}
		int nx, ny;
		for(int dir = 0; dir < 4; dir++){
			nx = dx[dir] + i;
			ny = dy[dir] + j;
			if(nx < 0 || ny < 0 || nx >= 200 || ny >= 200 || used[nx][ny] || map[nx].charAt(ny) == '.'){
				continue;
			}
			dfs(nx, ny);
		}
	}
	//
	void printLetter(ArrayList<point> a){
		int C = 20; 
		boolean[][] pic = new boolean[C+1][C+1];
		for(point p : a){
			pic[(int)(p.x * C)][(int)(p.y * C)] = true;
		}
		for(int i = 0; i <= C; i++){
			for(int j = 0;j <= C; j++){
				cout.print(pic[i][j]?'X':'.');
			}
			cout.println();
		}
		cout.println();
	}
	
	double distTo(point p, ArrayList<point> a){
		double res = Double.MAX_VALUE;
		for(point q : a){
			res = Math.min(res, Math.hypot(p.x - q.x, p.y - q.y));
		}
		return res;
	}	
	
	
	//

	
	
	double difference(ArrayList<point> a){
		double ret = 0, last = 0;
		for(point p: c){
			double min = 1E+20;
			for(point q: a){
				min = Math.min(min, Math.hypot(p.x - q.x, p.y - q.y));
			}
			last = min;
			ret += min;
		}
		ret += p2 - last * 2;
		return ret / (1.0 * c.size());
	}	
	
	
	
	
	
	
	
	
	private double checkG(ArrayList<point> a) {
		c = new ArrayList<point>();
		//
		c.add(new point(EPS, 1 - EPS));
		c.add(new point(EPS, p2));
		c.add(new point(p4, p8));
		c.add(new point(p2, 0));
		c.add(new point(p2, 2 * p3));
		c.add(new point(1 - p16, 3 * p8));
		c.add(new point(1.000 - EPS, p2));
		c.add(new point(1 - p16, 5 * p8));
		//
		c.add(new point(p2, p3));
		return difference(a);
	}	
	
	
	private double checkS(ArrayList<point> a) {
		c = new ArrayList<point>();
		//
		//c.add(new point(EPS, 1 - EPS));
		c.add(new point(p16, p2));
		c.add(new point(p4, EPS));
		c.add(new point(p8, p5));
		c.add(new point(p2, p4));
		c.add(new point(p2, p2));
		c.add(new point(p2, 3.0 * p4));
		c.add(new point(3 * p4, 1 - p16));
		c.add(new point(1.000 - p16, p16));
		//c.add(new point(1.0 - p16, 0.0));
		//
		c.add(new point(p2 - p8, 1));
		return difference(a);
	}
	
	
//
	
	
	private double checkA(ArrayList<point> a) {
		c = new ArrayList<point>();
		//
		c.add(new point(0, p2));
		c.add(new point(p4, 3.0 * p8));
		c.add(new point(p4, 5.0 * p8));
		c.add(new point(2 * p3, 1.0 * p4));
		c.add(new point(2 * p3, 3.0 * p4));
		c.add(new point(2 * p3, p2));
		c.add(new point(3 * p4, 1.0 * p8));
		c.add(new point(3 * p4, 7.0 * p8));
		c.add(new point(1.000, 0));
		c.add(new point(1.0, 1.0));
		//
		c.add(new point(0, 1));
		return difference(a);
	}
	
	
//
	
	private double checkB(ArrayList<point> a) {
		c = new ArrayList<point>();
		//
		c.add(new point(p16, p16));
		c.add(new point(p16, 3 * p4));
		c.add(new point(p4, p8));
		c.add(new point(p4, 1.0 - EPS));
		c.add(new point(p2, p16));
		c.add(new point(p2, 3 * p4));
		c.add(new point(3 * p4, p16));
		c.add(new point(3 * p4, 1 - p16));
		c.add(new point(1.00 - EPS, 0));
		c.add(new point(1.00 - EPS, 3 * p4));
		//
		c.add(new point(3 * p4, p2));
		return difference(a);
	}
	
	//
	
	private double checkE(ArrayList<point> a) {
		c = new ArrayList<point>();
		//
		c.add(new point(0, 0));
		c.add(new point(0, p2));
		c.add(new point(0, 1));
		c.add(new point(p2, 0.0));
		c.add(new point(p2, p2));
		c.add(new point(p2, 1));
		c.add(new point(1, 0));
		c.add(new point(1, p2));
		c.add(new point(1.00, 3 * p4));
		c.add(new point(1.0, 1));
		//
		c.add(new point(3 * p4, 1));
		return difference(a);
	}
	
	//
	
	private double checkF(ArrayList<point> a) {
		c = new ArrayList<point>();
		//
		c.add(new point(0, 0));
		c.add(new point(0, p2));
		c.add(new point(0, 1));
		c.add(new point(p4, 0.0));
		c.add(new point(p2, 0));
		c.add(new point(p2, p3));
		c.add(new point(p2, 2 * p3));
		c.add(new point(p2, 3 * p4));
		c.add(new point(3 * p4, 0));
		c.add(new point(1.0, 0));
		//
		c.add(new point(1, 1));
		return difference(a);
	}
	
	//
	
	private double checkP(ArrayList<point> a) {
		c = new ArrayList<point>();
		//
		c.add(new point(0, 0));
		c.add(new point(0, p2));
		c.add(new point(p4, 1.0));
		c.add(new point(p4, 1.0));
		c.add(new point(p4, p16));
		c.add(new point(0, p4));
		c.add(new point(p2, p2));
		c.add(new point(p2, 3 * p4));
		c.add(new point(3 * p4, p16));
		c.add(new point(1.0, p16));
		//
		c.add(new point(3 * p4, 1));
		return difference(a);
	}
	
	//
	
	private double checkH(ArrayList<point> a) {
		c = new ArrayList<point>();
		//
		c.add(new point(0, p16));
		c.add(new point(0, 1 - p16));
		c.add(new point(p2, 2 * p3));
		c.add(new point(p2, p3));
		c.add(new point(p2, p2));
		c.add(new point(1.00 - p16, p16));
		c.add(new point(1.00 - p16, 1));
		//
		c.add(new point(p4, p2));
		return difference(a);
	}
	
	//
	
	private double checkN(ArrayList<point> a) {
		c = new ArrayList<point>();
		//
		c.add(new point(0, p16));
		c.add(new point(0, 1 - p16));
		c.add(new point(p5, p5));
		c.add(new point(4 * p5, 4 * p5));
		c.add(new point(1 - p16, 1 - p16));
		c.add(new point(p2, EPS));
		c.add(new point(p2, 1));
		c.add(new point(1.00, p16));
		//
		c.add(new point(p4, p5));
		return difference(a);
	}
	
	//
	
	private double checkI(ArrayList<point> a) {
		double s1;
		c = new ArrayList<point>();
		//
		//c.add(new point(0, 3 * p8));
		c.add(new point(p4, p2));
		//c.add(new point(0, 5 * p8));
		c.add(new point(p4, p2));
		c.add(new point(p2, p2));
		c.add(new point(3 * p4, p2));
		//c.add(new point(1, 3 * p8));
		c.add(new point(1, p4));
		c.add(new point(1.00, p2));
		//c.add(new point(1.00, 5 * p8));
		//
		c.add(new point(p2, 0));
		s1 = difference(a);
		
		return s1;
	}
	
	//
	
	private double checkT(ArrayList<point> a) {
		double s1;
		c = new ArrayList<point>();
		//
		c.add(new point(0, 0));
		c.add(new point(0, p4));
		c.add(new point(0, p2));
		c.add(new point(0, 3 * p4));
		c.add(new point(0, 1));
		c.add(new point(p5, p2));
		c.add(new point(2 * p5, p2));
		c.add(new point(3 * p5, p2));
		c.add(new point(4 * p5, p2));
		c.add(new point(1.00, p2));
		//
		c.add(new point(2 * p3, 1));
		s1 = difference(a);
		
		return s1;
	}
	
	//
	
	private double checkK(ArrayList<point> a) {
		c = new ArrayList<point>();
		//
		c.add(new point(0, 0));
		c.add(new point(0, 1));
		c.add(new point(p4, 0.0));
		c.add(new point(p4, p2));
		c.add(new point(p2, 0));
		c.add(new point(4 * p6, p3));
		c.add(new point(5 * p6, 2 * p3));
		c.add(new point(p4, 0));
		c.add(new point(1.00, 0));
		c.add(new point(1.00, 1));
		//
		c.add(new point(p2, 1));
		return difference(a);
	}
	
	//
	
	private double checkL(ArrayList<point> a) {
		c = new ArrayList<point>();
		//
		c.add(new point(0, 0));
		c.add(new point(p5, 0));
		c.add(new point(2 * p5, 0));
		c.add(new point(3 * p5, 0));
		c.add(new point(4 * p5, 0));
		c.add(new point(1, 0));
		c.add(new point(1, 1));
		c.add(new point(1, p4));
		c.add(new point(1.00, p2));
		c.add(new point(1.00, 3 * p4));
		//
		c.add(new point(p2, p2));
		return difference(a);
	}
	
	//
	
	private double checkM(ArrayList<point> a) {
		c = new ArrayList<point>();
		//
		c.add(new point(0, p8));
		c.add(new point(0, 1 - p8));
		c.add(new point(p2, p3));
		c.add(new point(p2, 2 * p3));
		c.add(new point(3 * p5, p8));
		c.add(new point(3 * p5, 1 - p8));
		c.add(new point(1, p8));
		c.add(new point(1, 1 - p8));
		c.add(new point(1.00 - p5 / 2, p2 - p16));
		c.add(new point(1.00 - p5 / 2, p2 + p16));
		//
		c.add(new point(0, p2));
		return difference(a);
	}
	
	//
	
	private double checkV(ArrayList<point> a) {
		c = new ArrayList<point>();
		//
		c.add(new point(0, 0));
		c.add(new point(0, 1));
		c.add(new point(p4, p8));
		c.add(new point(p2, p4));
		c.add(new point(3 * p4, 3 * p8));
		c.add(new point(1, p2));
		c.add(new point(1, p2));
		c.add(new point(3 * p4, 5 * p8));
		c.add(new point(p2, 3 * p4));
		c.add(new point(p4, 7 * p8));
		//
		c.add(new point(p3, p2));
		return difference(a);
	}
	
	//
	
	private double checkW(ArrayList<point> a) {
		c = new ArrayList<point>();
		//
		c.add(new point(0, p16));
		c.add(new point(0, 1 - p16));
		c.add(new point(p5 / 2, p2 - p16));
		c.add(new point(p5 / 2, p2 + p16));
		c.add(new point(p2, p8));
		c.add(new point(p2, 3 * p8));
		c.add(new point(p2, 5 * p8));
		c.add(new point(p2, 7 * p8));
		c.add(new point(1, p4));
		c.add(new point(1, 3 * p4));
		//
		c.add(new point(1, p2));
		return difference(a);
	}

	public void run() {
		try {
			run2();
		} catch (Exception e) {
			e.printStackTrace();
			throw new RuntimeException("dfgfg");
		}
	}
}