1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
def test(s):
    #   print(s)
    if s in stest:
        if s in usetest:
            return(0)
        usetest.add(s)
        return(stest[s])
    l = list(s)
    ll = 0
    for strona in l:
        if strona == 'L':
            ll+=1
        else:
            ll-=1
            if ll<0:
                stest[s] = False
                return(False)
    stest[s] = (ll==0)
    return(ll==0)

def gen(s):
    if s in gentab:
        if s in usegentab:
            return(0)
        usegentab.add(s)
        return(gentab[s])
        
    if len(s) < 2:
        return(0)
    wyn = 0
    
    if test(s):
        wyn+=1
    for i in range(len(s)):
        wyn += gen(s[:i]+s[i+1:])
    gentab[s] = wyn
    usegentab.add(s)
    return(wyn)

gentab = {}
stest = {}
usegentab = set()
usetest = set()

def main():
    n = int(input())
    tab = []
    us = set()
    for _ in range(n):
        tab.append(input())
    for pd in tab:
        for kd in tab:
            usegentab.clear()
            usetest.clear()
            gentab.clear()
            #stest.clear()
            wyn = gen(pd+kd)
            print(wyn, "", end="")
        print()

main()