친구이자 적

'적의 적은 친구'라는 말이 있다. 이 말을 그대로 밀고 나가면 '적의 적의 적은 적'이 되고, 이런 식으로 계속 이어진다. 사람들 사이의 관계가 주어질 때, 두 사람이 서로 얼마나 친구인지 또는 적인지를 나타내는 총 관계 점수를 구하자.

첫째 줄에 데이터 세트의 개수 $N$ ($1 \le N \le 100$)이 주어진다. 각 데이터 세트는 다음과 같이 이어진다.

1. 첫째 줄에 이 데이터 세트에 등장하는 사람 수 $P$ ($1 \le P \le 9$)가 주어진다.
2. 다음 $P$개 줄에는 사람들 사이의 직접 관계를 나타내는 관계 행렬이 이름 R1 R2 ... RX ... RP 형식으로 주어진다. 이름은 알파벳과 숫자로만 이루어진 최대 20자의 문자열이고 서로 겹치지 않는다. $R_X$는 이 사람과 $X$번째 사람 사이의 관계이며 F는 친구, E는 적, N은 중립을 뜻한다. 예를 들어 어떤 줄이 Bob F E N이면 Bob은 관계 행렬 첫째 줄의 사람과 친구, 둘째 줄의 사람과 적, 셋째 줄의 사람과 중립이다. 자기 자신과의 관계는 언제나 중립이고, 관계는 양방향이다. 즉 Bob이 George와 친구면 George도 Bob과 친구다.
3. 마지막 줄에는 점수를 구할 사람의 이름이 하나 주어진다.

각 데이터 세트마다 한 줄에, 마지막 줄에 주어진 사람과 그 데이터 세트에 있는 모든 사람 사이의 총 관계 점수를 입력에 이름이 나온 순서대로 공백 하나로 구분해 출력한다. 자기 자신과의 점수는 0이고, 이 값도 함께 출력한다.

두 사람의 총 관계 점수는 둘 사이의 모든 직접 관계와 간접 관계 점수를 더한 값이다. 직접 관계는 위에서 설명한 관계 행렬로 정해진다. 간접 관계는 두 사람을 잇는 경로 가운데 관계를 두 개 이상 거치고, 같은 사람을 두 번 지나지 않으며, 중립 관계를 하나도 포함하지 않는 경로를 말한다. '적의 적'이나 '적의 친구의 적'이 여기에 해당한다. 직접 관계든 간접 관계든 경로 하나의 점수는 다음과 같다.

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

$x$는 경로에 있는 적 관계의 개수, $y$는 경로에 있는 관계의 총 개수다. 몇 가지 예를 들면 다음과 같다.

• 친구: $128 \times (-1)^0 \div 2^{1-1} = 128$
• 적: $128 \times (-1)^1 \div 2^{1-1} = -128$
• 친구의 친구: $128 \times (-1)^0 \div 2^{2-1} = 64$
• 적의 적: $128 \times (-1)^2 \div 2^{2-1} = 64$
• 적의 적의 적: $128 \times (-1)^3 \div 2^{3-1} = -32$

$P \le 9$이므로 $y$는 8을 넘지 않고, 모든 점수는 정수다.