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

Difficulty: interview

Starter code:

Solutions:
T=int(input())

for t in range(T):
    s=input()
    ans=0
    L=[]
    for i in [1,2,3,4,6,12]:
        x=i
        y=12//x
        E=[]
        for j in range(12):
            if(j%y==0):
                E.append("")
            E[-1]+=s[j]
        for j in range(y):
            c=0
            for z in range(i):
                if(E[z][j]=='X'):
                    c+=1
            if(c==i):
                ans+=1
                L.append(i)
                break
    print(ans,end=" ")
    for item in L:
        print(item,end="x")
        print(12//item,end=" ")
    print()


#!/usr/bin/env python3

def read_ints():
	return list(map(int, input().strip().split()))

t, = read_ints()

for _ in range(t):
	x = input()

	correct = []

	for a in [1, 2, 3, 4, 6, 12]:
		cor = False
		for c in range(0, 12//a):
			s = set(x[c::12//a])

			if len(s)==1 and 'X' in s:
				cor = True
				break

		if cor == True:
			correct.append("{}x{}".format(a, 12//a))
	
	print(len(correct), ' '.join(correct))
				




# http://codeforces.com/contest/400/problem/0
# Codeforces : A. Inna and choose options

liste_a = (1, 2, 3, 4, 6, 12)
liste_results = []

def process(essai):
    nonlocal liste_results
    liste_av = [0]
    for a in liste_a:
        b = 12 // a
        for r in range(b):
            if essai[r::b] == 'X'*a:
                liste_av[0] += 1
                liste_av.append('{}x{}'.format(a,b))
                break
    liste_av[0] = str(liste_av[0])
    liste_results.append(liste_av)




t = int(input())
for k in range(t):
    essai = input()
    process(essai)

for s in liste_results:
    print(*s)


t = int(input())
for i in range(t):
    s = input().strip()
    cnt = 0
    ans = []
    for b in [1, 2, 3, 4, 6, 12]:
        List = []
        a = 12 // b
        for begin in range(b):
            column = ''
            j = begin
            while j < 12:
                column += s[j]
                j += b
            List.append(column)
        #print(i, b, List)
        if 'X' * a in List:
            cnt += 1
            ans.append((a, b))
    print(cnt, end = ' ')
    for pair in sorted(ans):
        print('x'.join(map(str, pair)), end = ' ')
    print()


def test(s):
    res = []
    for i in [[1, 12], [2, 6], [3, 4], [4, 3], [6, 2], [12, 1]]:
        a = [["O" for i in range(i[1])] for j in range(i[0])]
        for j in range(i[0]):
            for k in range(i[1]):
                a[j][k] = s[j * i[1] + k]
        if check(a):
            res.append(i)
    return res

def check(a):
    for i in range(len(a[0])):
        if not "O" in [a[j][i] for j in range(len(a))]:
            return True
    return False

t = int(input())
for i in range(t):
    s = input().strip()
    x = test(s)
    print(len(x), end=" ")
    for j in x:
        print(j[0], "x", j[1], sep="", end=" ")
    print()


for _ in range(int(input())):
    cards = input()
    count = 0
    output = ''
    if 'X' in cards:
        count += 1
        output += ' 1x12'
    for q, p in zip(cards[:6], cards[6:]):
        if q == p == 'X':
            count += 1
            output += ' 2x6'
            break
    for q, p, r in zip(cards[:4], cards[4:8], cards[8:]):
        if q == p == r == 'X':
            count += 1
            output += ' 3x4'
            break
    for q, p, r, s in zip(cards[:3], cards[3:6], cards[6:9], cards[9:]):
        if q == p == r == s == 'X':
            count += 1
            output += ' 4x3'
            break
    for q, p, r, s, t, u in zip(cards[:2], cards[2:4], cards[4:6], cards[6:8], cards[8:10], cards[10:]):
        if q == p == r == s == t == u == 'X':
            count += 1
            output += ' 6x2'
            break
    if 'O' not in cards:
        count += 1
        output += ' 12x1'
    print(str(count) + output)


n = int(input())
ab = [12, 6, 4, 3, 2, 1]
lst = [list(input()) for i in range(n)]
res = [[0] for i in range(n)] 
for pr in range(n):
    for elem in ab:
        for i in range(elem):
            x = 1
            for j in range(0, 12, elem):
                if lst[pr][i + j] == "O":
                    x = 0
            if x == 1 and str(12 // elem) + "x" + str(elem) not in res[pr]: 
                res[pr][0] += 1
                res[pr].append(str(12 // elem) + "x" + str(elem))
for i in range(len(res)):
    print(" ".join(map(str, res[i])))


t = int(input())
for i in range(t):
    s = input()
    ans = ""
    count = 0
    for j in range(1, 13):
        flag = False
        if 12 % j == 0:
            for p in range(12 // j):
                q = p
                while q < 12 and s[q] == "X":
                    q += 12 // j
                if q >= 12:
                    flag = True
        if flag:
            ans += str(j) + "x" + str(12 // j) + " "
            count += 1
    print(count, ans[:-1])

n=int(input())
for i in range(n):
    a=input()
    c=0
    p=''
    if 'XXXXXXXXXXXX'==a:
        print('6 1x12 2x6 3x4 4x3 6x2 12x1')
        continue
    if 'X' in a:
        p=p+'1x12'
        c+=1
        if 'XX'==(a[0]+a[6]) or 'XX'==(a[1]+a[7]) or 'XX' ==(a[2]+a[8]) or 'XX' ==(a[3]+a[9]) or 'XX' ==(a[4]+a[10]) or 'XX' ==(a[5]+a[11]):
            c+=1
            p+=' 2x6'
        if 'XXX'==(a[0]+a[4]+a[8]) or 'XXX'==(a[1]+a[5]+a[9]) or 'XXX'==(a[2]+a[6]+a[10]) or 'XXX'==(a[3]+a[7]+a[11]):
            p+=' 3x4'
            c+=1
        if 'XXXX'==(a[0]+a[3]+a[6]+a[9]) or 'XXXX'==(a[1]+a[4]+a[7]+a[10]) or 'XXXX'==(a[2]+a[5]+a[8]+a[11]):
            c+=1
            p+=' 4x3'
        if 'XXXXXX'==(a[0]+a[2]+a[4]+a[6]+a[8]+a[10])or 'XXXXXX'==(a[1]+a[3]+a[5]+a[7]+a[9]+a[11]):
            c+=1
            p+=' 6x2'
        print(c,p)
                        

    else:
        print(0)
        


n = int(input())
p = 0
f = True
for k in range(n):
    s = input().strip()
    ot = set()
    for i in range(1, 13):
        if i == 5 or i == 7 or i == 9 or i == 10 or i == 11 or i == 8:
            continue
        for t in range(i):
            p = True
            for j in range(t, 12, i):
                if s[j] == 'O':
                    p = False
            if p:
                ot.add(i)
    ot = list(reversed(sorted(list(ot))))
    print(len(ot), end = ' ')
    for i in ot:
        print(str(12//i)+'x'+str(i), end = ' ')
    print()

from functools import reduce

def sol(l):
  if not "X" in l: return "0"
  l = l.replace("O","0").replace("X","1")
  res = [ "%ix%i" % (12//i, i) for i in (12,6,4,3,2,1) if reduce(lambda x, y: x&y, [int(l[i*j:i*j+i],2) for j in range(12//i)], -1)]
  return ("%i %s" % (len(res), " ".join(res)))

n = int(input())
print("\n".join([sol(input()) for i in range(n)]))

from functools import reduce
print("\n".join([(lambda x:("%i %s" % (len(x), " ".join(x))))((lambda h:[ "%ix%i" % (12//i, i) for i in (12,6,4,3,2,1) if reduce(lambda x, y: x&y, [int(h.replace("O","0").replace("X","1")[i*j:i*j+i],2) for j in range(12//i)], -1)])(input())) for i in range(int(input()))]))

t = int(input())
n = 12
while t > 0:
    ans = []
    t = t - 1
    s = input()
    for i in range(n):
        r = i+1
        if n%r != 0:
            continue
        c = n//r
        flag = False
        for j in range(c):
            id = j
            ff = False
            while id < n:
                if s[id] != 'X':
                    ff = True
                    break
                id = id + c
            if ff == False:
                flag = True
                break
        if flag == True:
            ans.append((r, c))

    print(len(ans), end = '')
    for i in range(len(ans)):
        print(' ', ans[i][0], 'x', ans[i][1], sep = '', end = '')
    print('')


q = [12, 6, 4, 3, 2, 1]
p = {12 // i: 'X' * i for i in q}
r = {i: str(12 // i) + 'x' + str(i) for i in q}
for i in range(int(input())):
    s, t = [], input()
    for j in q:
        if any(t[k :: j] == p[j] for k in range(j)): s.append(r[j])
    print(len(s), ' '.join(s))

#!/usr/local/bin/python33
n = int(input())

for i in range(n):
	cnt = 0
	answ = ['1x12', '2x6', '3x4', '4x3', '6x2', '12x1']
	answb = [False, False, False, False, False, False]
	instr = input()

	if 'X' in instr:
		cnt += 1
		answb[0] = True
	for j in range(6):
		if (instr[j] == instr[6 + j] == 'X'):
			cnt += 1
			answb[1] = True
			break
	for j in range(4):
		if (instr[j] == instr[4 + j] == instr[8 + j] == 'X'):
			cnt += 1
			answb[2] = True
			break
	for j in range(3):
		if (instr[j] == instr[3 + j] == instr[6 + j] == instr[9 + j] == 'X'):
			cnt += 1
			answb[3] = True
			break
	for j in range(2):
		if (instr[j] == instr[2 + j] == instr[4 + j] == instr[6 + j] == instr[8 + j] == instr[10 + j] == 'X'):
			cnt += 1
			answb[4] = True
			break
	if not 'O' in instr:
		cnt += 1
		answb[5] = True

	print(cnt, end = ' ')
	for i in range(6):
		if answb[i]:
			print(answ[i], end = ' ')
	print()

t = int(input())
for i in range(0, t):
    str = input()
    answer = []
    p = [1, 2, 3, 4, 6, 12]
    for j in range(0, len(p)):
        d1, d2 = p[j], 12 // p[j]
        cnt = [0 for h in range(0, d2)]
        for i2 in range(0, 12):
            tt = i2 % d2
            cnt[tt] += (str[i2] == 'X')
        ans_cand = False
        for i2 in range(0, d2):
            if cnt[i2] == d1:
                ans_cand = True
        if ans_cand:
            answer.append('%dx%d' % (d1, d2))
    print(len(answer), end = ' ')
    for j in range(0, len(answer)):
        print(answer[j], end = ' ')
    print()

t = int(input().strip())
for i in range(t):
    s = input()
    ans = []
    for h in [x for x in range(1, 13) if 12 % x == 0]:
        good = False
        w = 12 // h
        for k in range(w):
            ok = True
            for l in range(h):
                if s[l * w + k] != 'X':
                    ok = False
            if ok:
                good = True
        if good:
            ans.append(str(h) + "x" + str(w))
    print(str(len(ans)) + " " + " ".join(ans))

T=int(input())

while T>=1:
    T-=1
    a=input()
    list=[]
    for i in range(1,13):
        if 12 % i==0:
            l=12//i
            for j in range(0,l):
                for k in range(0,i):
                    if a[k*l+j]!='X':
                        break
                else:
                    break
            else:
                continue
            list.append(i)
    print(len(list),end=' ')
    for i in range(0,len(list)):
        print(str(list[i])+'x'+str(12//list[i]),end=' ')
    print()


a=int(input())
while a:
    l=[]
    b=input()
    if((b.count("X"))>0):
        l.append("1x12")
    if((b[:6].count("X"))>0):
        p=[i for i in range(6) if b[i]=='X']
        for i in p:
            if(b[i:12:6]=='XX'):
                l.append("2x6")
                break
    if((b[:4].count("X"))>0):
        p=[i for i in range(4) if b[i]=='X']
        for i in p:
            if(b[i:12:4]=="XXX"):
                l.append("3x4")
                break
    if((b[:3].count("X"))>0):
        p=[i for i in range(3) if b[i]=='X']
        for i in p:
            if(b[i:12:3]=="XXXX"):
                l.append("4x3")
                break
    if((b[:2].count("X"))>0):
        p=[i for i in range(2) if b[i]=='X']
        for i in p:
            if(b[i:12:2]=="XXXXXX"):
                l.append("6x2")
                break
    if(b.count("X")==12):
        l.append("12x1")
    print(len(l),end=" ")
    if(len(l)>0):
        for i in l:
            print(i,end=" ")
    print()
    a-=1

def test_col(s, a, b, col):
	res = True
	for i in range(0, a):
		if s[i * b + col] != 'X':	
			res = False
	return res	

def test_all_cols(s, a):
	b = len(s) // a
	if a * b != len(s):
		return False
	else:
		res = False
		for i in range(0, b):
			res = res or test_col(s, a, b, i)
		return res

	
n = int(input())
for i in range(0, n):
	s = input()
	slen = len(s)
	cvariants  = 0 
	variants = ""
	for a in range(1, slen + 1):		
		if (test_all_cols(s, a)):
			cvariants += 1
			variants += str(a) + "x" + str(slen // a) + " "
	print(str(cvariants), variants)
	


# -*- coding: UTF-8 -*-
def evaluate(origin_str):
    ans = []
    for i in [1,2,3,4,6,12]:
        last_idx = int(12 / i)
        flags = [1 for i in range(0,last_idx)]
        if (i == 1):
            flag = False
            for ch in origin_str:
                if (ch == 'X'):
                    flag = True
            if (flag):
                ans.append([i,last_idx])
        else:
            for j in range(0,last_idx):
                tmp = []
                k = j - last_idx
                for x in range(0,i):
                    k += last_idx
                    tmp.append(k)
                for l in tmp:
                    ch = origin_str[l]
                    if (ch != 'X'):
                        flags[j] = 0
            if (sum(flags) != 0):
                ans.append([i,last_idx])
    s = ""
    for a in ans:
        s += str(a[0])+"x"+str(a[1]) + " "
    print(str(len(ans)) + " " + s)
 
def main():
    n = int(input())
    for i in range(0,n):
        evaluate(input())
 
main()


n = int(input())


for _ in range(n):
    mystr = input()
    answer = []
    
    divisibles = [1,2,3,4,6,12]
    for i in divisibles:
        flag=0
        
        for j in range(0,12//i):
            columnSet = set(mystr[j::12//i])
            if len(columnSet)==1 and "X" in columnSet:
                flag=1
                break

        if flag==1:
           answer.append("{}x{}".format(i,12//i));
    print(len(answer), " ".join(answer))


t = int(input())
for _ in range(t):
  s = input()
  b = []
  for n in [1, 2, 3, 4, 6, 12]:
    m = 12 // n
    for j in range(m):
      if s[j::m] == "X" * n:
        b += [(n, m)]
        break
  print(len(b), ' '.join(str(x) + "x" + str(y) for x, y in b))

t = int(input())
ans = [[] for i in range(t)]
for i in range(t):
    
    s = input()    
    for a in range(1, 13):
        
        
        if 12 % a != 0:
            continue
        b = 12 // a
        c = [[] for h in range(b)]
        for h in range(b):
            for k in range(a):
                c[h].append(s[k * b + h])
        if a == 3:
            a = 3        
        T = True
        for h in range(b):
            if T:
                ok = True
                for k in range(a):
                    if c[h][k] == 'O':
                        ok = False
                if ok:
                    ans[i].append([a, b])
                    T = False
                    break
for i in range(t):
    print(len(ans[i]), end = ' ')
    for z in ans[i]:
        print(z[0], end = '')
        print('x', end= '')
        print(z[1], end = ' ')
    print()


def do(string):
    num = 0
    ok = []
    for i in [12, 6, 4, 3, 2, 1]:
        for j in range(0, i):
            if string[j::i] == 'X' * int(12/i):
                ok.append(str(int(12/i))+'x'+str(i))
                num += 1
                break

    ok = [str(num)] + ok
    print(' '.join(ok))

for i in range(int(input())):
    do(input())