Frenemies

You have probably heard the saying "the enemy of my enemy is my friend". Push it one step further and you get "the enemy of my enemy of my enemy is my enemy", and so on. Given a set of relationships, work out how much of a friend or an enemy two people are, expressed as a total relationship score.

The first line contains a single integer $N$ ($1 \le N \le 100$), the number of data sets. Each data set is given as follows.

1. The first line contains a single integer $P$ ($1 \le P \le 9$), the number of people in this data set.
2. The next $P$ lines contain a relationship matrix that describes the direct relationships between the people, in the format Name R1 R2 ... RX ... RP. Name is a unique name of up to twenty contiguous alphanumeric characters, and $R_X$ is the relationship between this person and person $X$, where F means a friend, E means an enemy, and N means a neutral relationship. For example, a line reading Bob F E N means Bob is a friend of the person on the first line of the relationship matrix, an enemy of the person on the second line, and neutral toward the person on the third line. A person is always neutral toward themselves, and relationships are bi-directional, so if Bob is a friend of George then George is a friend of Bob.
3. The last line of the data set contains a single name. The scores are computed between that person and everyone in the data set.

For each data set, print one line with the total relationship scores between the name given on the last line of the data set and every person in the data set, separated by single spaces and in the order the names appear in the input. The score with themselves is 0 and is printed as well.

The total relationship score between two people is the sum of the scores of all direct and indirect relationships between them. Direct relationships come from the matrix described above. An indirect relationship is a path connecting the two people that follows two or more relationships, never passes through the same person twice, and contains no neutral relationship. An enemy of an enemy, or an enemy of a friend of an enemy, is such a path. Whether direct or indirect, the score of one path is

$$\frac{128 \times (-1)^x}{2^{y-1}}$$

where $x$ is the number of enemy relationships on the path and $y$ is the total number of relationships on the path. Some examples follow.

• friend: $128 \times (-1)^0 \div 2^{1-1} = 128$
• enemy: $128 \times (-1)^1 \div 2^{1-1} = -128$
• friend of a friend: $128 \times (-1)^0 \div 2^{2-1} = 64$
• enemy of an enemy: $128 \times (-1)^2 \div 2^{2-1} = 64$
• enemy of an enemy of an enemy: $128 \times (-1)^3 \div 2^{3-1} = -32$

Since $P \le 9$, $y$ never exceeds 8 and every score is an integer.