단어 방정식

0과 1로 이루어진 비어 있지 않은 모든 수열을 이진 단어라고 한다. 단어 방정식은 다음과 같은 형태의 등식이다.

$x_1 x_2 \dots x_l = y_1 y_2 \dots y_r$

여기서 각 $x_i$와 각 $y_j$는 이진 숫자(0 또는 1)이거나 변수(영어 소문자)이다.

모든 변수에는 고정된 길이가 정해져 있다. 이는 그 변수에 대입할 수 있는 이진 단어의 자릿수이다. 단어 방정식을 푼다는 것은, 각 변수마다 그 변수의 길이와 정확히 같은 길이의 이진 단어를 하나씩 배정하여, 모든 변수를 배정한 단어로 치환했을 때 좌변과 우변이 같은 이진 단어가 되도록 만드는 것이다.

예를 들어 변수 $a, b, c, d, e$의 길이가 각각 $4, 2, 4, 4, 2$이고 방정식이

$1bad1 = acbe$

라면, 이 방정식의 서로 다른 해는 정확히 $16$개이다.

주어진 방정식에 대해 서로 다른 해가 몇 개인지 구하여라. 프로그램은 다음을 수행해야 한다.

• 표준 입력에서 방정식의 개수와 각 방정식의 설명을 읽는다.
• 각 방정식의 해의 개수를 구한다.
• 그 결과를 표준 출력에 쓴다.

첫째 줄에 방정식의 개수 $x$ ($1 \le x \le 5$)가 주어진다. 이어서 $x$개의 방정식 설명이 사이에 빈 줄 없이 주어진다. 각 방정식의 설명은 정확히 여섯 줄로 이루어진다.

1. 방정식에 등장하는 서로 다른 변수의 개수 $k$ ($0 \le k \le 26$). 변수는 영어 소문자 중 앞에서부터 $k$개이다.
2. 공백 하나로 구분된 $k$개의 양의 정수로, 변수 $a, b, \dots$의 길이를 순서대로 나타낸다(첫 번째 수가 $a$의 길이, 두 번째 수가 $b$의 길이, 이런 식이다). $k = 0$이면 이 줄은 비어 있다.
3. 좌변의 길이 $l$. 좌변에 적힌 숫자와 변수 문자의 개수이다.
4. 좌변. 숫자와 변수 문자를 공백 없이 이어 붙인 문자열이다.
5. 우변의 길이 $r$.
6. 우변. 좌변과 같은 방식으로 표현된다.

각 변에서 숫자의 개수와 (모든 등장을 세어 더한) 변수 길이의 합을 합한 값은 $10\,000$ 이하이다.

각 $i$ ($1 \le i \le x$)에 대해, $i$번째 줄에 $i$번째 방정식의 서로 다른 해의 개수를 출력한다.