{"raw_statement":[{"iden":"statement","content":"You are given a set of n strings such that all characters in the strings are '_a_', '_b_', or '_c_'.\n\nAlso, 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.\n\nA _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.\n\nA _palindrome_ is a word, phrase, number, or other sequence of characters which reads the same backward as forward, such as \"_madam_\" or \"_racecar_\".\n\nThe first line contains an integer T, where T is the number of test cases.\n\nThe 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.\n\nThen 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.\n\nThen 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.\n\nFor 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.\n\nAs 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.\n\n"},{"iden":"input","content":"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."},{"iden":"output","content":"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."},{"iden":"note","content":"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."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T \\in \\mathbb{Z}^+ $ be the number of test cases.  \nFor each test case:  \n- Let $ n \\in \\mathbb{Z}^+ $ be the number of strings, $ q \\in \\mathbb{Z}^+ $ the number of queries.  \n- 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 $.  \n- Let $ \\text{pal}(s) $ denote the number of palindromic substrings in string $ s $.  \n- Each string $ s_i $ is associated with index $ i \\in \\{1, \\dots, n\\} $.  \n\n**Constraints**  \n1. $ 1 \\leq T \\leq \\text{unspecified} $  \n2. $ 1 \\leq n \\leq 10^4 $, $ 1 \\leq q \\leq 10^5 $  \n3. $ 1 \\leq |s_i| \\leq 30 $, $ s_i \\in \\{a, b, c\\}^* $, all $ s_i $ unique  \n4. For each query, $ a, b \\in \\{s_1, \\dots, s_n\\} $  \n\n**Objective**  \nFor each query $ (a, b) $:  \nLet $ i_a $ be the index of string $ a $, $ i_b $ the index of string $ b $.  \nOutput:  \n$$\n\\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\\}\n$$","simple_statement":"Given n strings (each made of 'a', 'b', 'c', length ≤ 30), and q queries.  \nFor each query, you're given two strings a and b from the set.  \nFind which one of them has more palindrome substrings.  \nIf tied, pick the one with the smaller index (1-based).  \nPrint the index of the chosen string for each query.","has_page_source":false}