You are given a set of n strings such that all characters in the strings are '_a_', '_b_', or '_c_'.
Also, you are given q queries, such that each query consisting of two strings a and b. The answer of each query is the index of the string with the most number of palindrome substrings between strings a and b from the given set.
A _substring_ of the string s is a sequence sl, sl + 1, ..., sr for some integers (l, r) such that (1 ≤ l ≤ r ≤ n), where n is the length of the string s.
A _palindrome_ is a word, phrase, number, or other sequence of characters which reads the same backward as forward, such as "_madam_" or "_racecar_".
The first line contains an integer T, where T is the number of test cases.
The first line of each test case contains two integers n and q (1 ≤ n ≤ 104) (1 ≤ q ≤ 105), where n is the number of strings, and q is the number of queries.
Then n lines follow, each line contains a non-empty string with length no more than 30, giving the strings. All characters in the strings are '_a_', '_b_', or '_c_'. It is guaranteed that all strings are unique. The given strings are numbered from 1 to n.
Then q lines follow, each line contains two strings a and b, giving the queries. It is guaranteed that strings a and b exist in the given set of strings.
For each query, print a single line containing the index of the string with the most number of palindrome substrings between the given strings a and b. If there are more than one answer, print the lowest index.
As input/output can reach huge size it is recommended to use fast input/output methods: for example, prefer to use _scanf/printf_ instead of _cin/cout_ in C++, prefer to use _BufferedReader/PrintWriter_ instead of _Scanner/System.out_ in Java.
## Input
The first line contains an integer T, where T is the number of test cases.The first line of each test case contains two integers n and q (1 ≤ n ≤ 104) (1 ≤ q ≤ 105), where n is the number of strings, and q is the number of queries.Then n lines follow, each line contains a non-empty string with length no more than 30, giving the strings. All characters in the strings are '_a_', '_b_', or '_c_'. It is guaranteed that all strings are unique. The given strings are numbered from 1 to n.Then q lines follow, each line contains two strings a and b, giving the queries. It is guaranteed that strings a and b exist in the given set of strings.
## Output
For each query, print a single line containing the index of the string with the most number of palindrome substrings between the given strings a and b. If there are more than one answer, print the lowest index.
[samples]
## Note
As input/output can reach huge size it is recommended to use fast input/output methods: for example, prefer to use _scanf/printf_ instead of _cin/cout_ in C++, prefer to use _BufferedReader/PrintWriter_ instead of _Scanner/System.out_ in Java.
**Definitions**
Let $ T \in \mathbb{Z}^+ $ be the number of test cases.
For each test case:
- Let $ n \in \mathbb{Z}^+ $ be the number of strings, $ q \in \mathbb{Z}^+ $ the number of queries.
- Let $ S = (s_1, s_2, \dots, s_n) $ be a sequence of $ n $ distinct non-empty strings over alphabet $ \{a, b, c\} $, with $ |s_i| \leq 30 $.
- Let $ \text{pal}(s) $ denote the number of palindromic substrings in string $ s $.
- Each string $ s_i $ is associated with index $ i \in \{1, \dots, n\} $.
**Constraints**
1. $ 1 \leq T \leq \text{unspecified} $
2. $ 1 \leq n \leq 10^4 $, $ 1 \leq q \leq 10^5 $
3. $ 1 \leq |s_i| \leq 30 $, $ s_i \in \{a, b, c\}^* $, all $ s_i $ unique
4. For each query, $ a, b \in \{s_1, \dots, s_n\} $
**Objective**
For each query $ (a, b) $:
Let $ i_a $ be the index of string $ a $, $ i_b $ the index of string $ b $.
Output:
$$
\arg\min_{i \in \{i_a, i_b\}} \left\{ i \,\middle|\, \text{pal}(s_i) = \max\left(\text{pal}(s_{i_a}), \text{pal}(s_{i_b})\right) \right\}
$$