Problem: There always is something to choose from! And now, instead of "Noughts and Crosses", Inna choose a very unusual upgrade of this game. The rules of the game are given below:

There is one person playing the game. Before the beginning of the game he puts 12 cards in a row on the table. Each card contains a character: "X" or "O". Then the player chooses two positive integers a and b (a·b = 12), after that he makes a table of size a × b from the cards he put on the table as follows: the first b cards form the first row of the table, the second b cards form the second row of the table and so on, the last b cards form the last (number a) row of the table. The player wins if some column of the table contain characters "X" on all cards. Otherwise, the player loses.

Inna has already put 12 cards on the table in a row. But unfortunately, she doesn't know what numbers a and b to choose. Help her win the game: print to her all the possible ways of numbers a, b that she can choose and win.

Input

The first line of the input contains integer t (1 ≤ t ≤ 100). This value shows the number of sets of test data in the input. Next follows the description of each of the t tests on a separate line.

The description of each test is a string consisting of 12 characters, each character is either "X", or "O". The i-th character of the string shows the character that is written on the i-th card from the start.

Output

For each test, print the answer to the test on a single line. The first number in the line must represent the number of distinct ways to choose the pair a, b. Next, print on this line the pairs in the format axb. Print the pairs in the order of increasing first parameter (a). Separate the pairs in the line by whitespaces.

Examples

Input

4
OXXXOXOOXOOX
OXOXOXOXOXOX
XXXXXXXXXXXX
OOOOOOOOOOOO


Output

3 1x12 2x6 4x3
4 1x12 2x6 3x4 6x2
6 1x12 2x6 3x4 4x3 6x2 12x1
0

Solution (in JAVA):

Solution:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintStream;
import java.io.Reader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class A {

	public A() 
	{
		Scanner s = new Scanner();
		PrintStream p = System.out;
		
		StringBuilder sb = new StringBuilder();
		//int[] factors = {1, 2, 3, 4, 6, 12};
		int[] factors = {12, 6, 4, 3, 2, 1};
		ArrayList<Integer> valid = new ArrayList<Integer>();
		
		int n = s.nextInt();
		for (int i = 0; i < n; i++)
		{
			String str = s.next();
			
			
		
			for (int j = 0; j < 6; j++)
			{
				int skip = factors[j];
				
				boolean add = false;
				//System.out.println(str);
				for (int k = 0 ; k < skip; k++)
					
				{
					boolean all = true;
					for (int l = k; l < 12; l += skip)
					{
						if (str.charAt(l) == 'O')
						{
							all = false;
							//System.out.println("WOOPS");
						}
						//System.out.println(i + ", " + j + ", " + k + ", " + l);
					}
					if (all == true)
					{
						add = true;
						//System.out.println("Add = true");
					}
				}
				if (add)
				{
					valid.add(skip);
					//System.out.println(skip);
				}
				
				//System.out.println("");
				
			}
			
			
			sb.append(valid.size()).append(" ");
			if (valid.contains(12))
			{
				sb.append("1x12 ");
			}
			if (valid.contains(6))
			{
				sb.append("2x6 ");
			}
			if (valid.contains(4))
			{
				sb.append("3x4 ");
			}
			if (valid.contains(3))
			{
				sb.append("4x3 ");
			}if (valid.contains(2))
			{
				sb.append("6x2 ");
			}
			if (valid.contains(1))
			{
				sb.append("12x1 ");
			}
			sb.append('\n');
			valid.clear();
		}
		
		System.out.println(sb.toString());
		
		
	}
	
	
	
	
	public static void main(String[] args) {
		new A();
	}

	public static class Scanner {
		BufferedReader br;
		StringTokenizer st;

		public Scanner(Reader in) {
			br = new BufferedReader(in);
		}

		public Scanner() {
			this(new InputStreamReader(System.in));
		}

		String next() {
			while (st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}

		int nextInt() {
			return Integer.parseInt(next());
		}

		long nextLong() {
			return Long.parseLong(next());
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}

		// Slightly different from java.util.Scanner.nextLine(),
		// which returns any remaining characters in current line,
		// if any.
		String readNextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (IOException e) {
				e.printStackTrace();
			}
			return str;
		}

		public int[] readNextLineInts(int numberOfInts) {
			int[] ints = new int[numberOfInts];
			for (int i = 0; i < numberOfInts; i++)
				ints[i] = nextInt();
			return ints;
		}
		
		public double[] readNextLineDoubles(int numberOfDoubles) {
			double[] doubles = new double[numberOfDoubles];
			for (int i = 0; i < numberOfDoubles; i++)
				doubles[i] = nextDouble();
			return doubles;
		}
		// --------------------------------------------------------
	}

	
	public boolean isPrime(int n)
	{
		for (int i = 2; i <= Math.sqrt(n);i++)
		{
			if (n % i == 0)
			{
				return false;
			}
		}
		return true;
	}
	
	/**
	 * Precondition: n is at least 0
	 * Note: it is many times more efficient to use isPrime(int n)
	 * for a single or a few numbers. This method is just for a large number of
	 * primes and is more efficient at exactly what it does.
	 * 
	 * It utilizes all previous primes to calculate all the next few primes. 
	 * Suprisingly, isPrime is not called here due to the difference.
	 * 
	 * @param n The number of primes you want. 
	 * If n=0, an empty array is returned
	 * @return  An array of the first n primes
	 */
	public ArrayList<Integer> firstNPrimes(int n)
	{
		ArrayList<Integer> primes = new ArrayList<Integer>();
		
		int numToTest = 2;
		
		while (primes.size() < n)
		{
			boolean prime = true;
			for (int i = 0; i < primes.size() && primes.get(i) <= Math.sqrt(numToTest); i++)
			{
				if (numToTest % primes.get(i) == 0)
					prime = false;
			}
			if (prime)
			{
				primes.add(numToTest);
				System.out.println(numToTest);
			}
			numToTest++;
		}
		return primes;
	}
	
	public class Loc implements Comparable<Loc>, Cloneable
	{
		public int x, y;
		public Loc(int x, int y)
		{
			this.x = x;
			this.y = y;
		}
		
		public int compareTo(Loc other) {
			return this.x - other.x;
		}
		
		public boolean equals(Object other)
		{
			return other instanceof Loc && ((Loc)other).x == this.x
					&& ((Loc)other).y == this.y;
		}
		
		public Loc clone()
		{
			return new Loc(this.x, this.y);
		}
		
		public String toString()
		{
			return x + " " + y;
		}
	}
	
	
//	public int[] largestIncreasingSubSequence()
//	{
//		
//	}
	
	
	/**
	 * ArrayList is NOT modified
	 * @param ints
	 * @return
	 */
	public ArrayList<Integer> firstIncreasingSequence(ArrayList<Integer> ints)
	{
		ArrayList<Integer> toReturn = new ArrayList<Integer>();
		if (ints.size() == 0)
			return toReturn;
		toReturn.add(ints.get(0));
		for (int i = 1; i < ints.size(); i++)
			if (ints.get(i) > ints.get(i - 1))
				toReturn.add(ints.get(i));
			else
				break;
		return toReturn;
	}
	
	
	/**
	 * ArrayList is NOT modified
	 * @param ints
	 * @return
	 */
	public ArrayList<Integer> lastDecreasingSequence(ArrayList<Integer> ints)
	{
		ArrayList<Integer> toReturn = new ArrayList<Integer>();
		if (ints.size() == 0)
			return toReturn;
		toReturn.add(0, ints.get(ints.size() - 1));
		for (int i = ints.size() - 2; i >= 0; i--)
		{
			if (ints.get(i) > ints.get(i + 1))
			{	
				toReturn.add(0, ints.get(i));
			}
			else
				break;
		}
		return toReturn;
	}
	
	/**
	 * ArrayList is NOT modified
	 * @param ints
	 * @return
	 */
	public ArrayList<Integer> firstIncreasingOrEqualSequence(ArrayList<Integer> ints)
	{
		ArrayList<Integer> toReturn = new ArrayList<Integer>();
		if (ints.size() == 0)
			return toReturn;
		toReturn.add(ints.get(0));
		for (int i = 1; i < ints.size(); i++)
			if (ints.get(i) >= ints.get(i - 1))
				toReturn.add(ints.get(i));
			else
				break;
		return toReturn;
	}
	
	public ArrayList<Integer> lastDecreasingOrEqualSequence(ArrayList<Integer> ints)
	{
		ArrayList<Integer> toReturn = new ArrayList<Integer>();
		if (ints.size() == 0)
			return toReturn;
		toReturn.add(0, ints.get(ints.size() - 1));
		for (int i = ints.size() - 2; i >= 0; i--)
		{
			if (ints.get(i) >= ints.get(i + 1))
			{	
				toReturn.add(0, ints.get(i));
			}
			else
				break;
		}
		return toReturn;
	}
}