CP Ad Agency has a billboard in Dhaka. The billboard contains an array S of n strings consisting of English alphabets. The strings are made of LED lights. So the agency needs to keep some strings on and some strings off for an ad each day. But, each day the agency is given a range [l. r]. The strings outside the range must be kept off on that day. Now, the agency has to decide which strings to keep on and which to keep off such that the lit on strings maintaining the order in S are concatenated to form a palindrome P. As the agency always wants the maximum profit each day, the formed palindrome P needs to be the longest possible. Now for q days, it’s your task to help the agency to find the length of the longest P the agency can make by choosing some strings from S with the range [l, r] of each day.

The first line will contain a single integer T (1 ≤ T ≤ 100). Each test case will start with two integers n (1 ≤ n ≤ 200) and q (1 ≤ q ≤ 10⁴) where n denotes the number of strings in array S and q denotes the number of queries. The second line of each test case will contain n space-separated strings. The following q lines of each test case will contain two integers l and r (1 ≤ l ≤ r ≤ n). All the n strings consist of english lowercase and uppercase letters and a string’s length will not be greater than 10. In any input file, it is guaranteed that the sum of n over all test cases won’t exceed 2000 as well as the sum of q won’t exceed 10⁵.

Input file is large. Please be sure to use faster input/output methods.

For the first line of each test case, print “Case x:” where x is the test case number. For the following q lines of each test case, print an integer which is the length of the longest P you can make by choosing some strings from the sub-array S_lS_{l + 1}…S_{r - 1}S_r.

Contest: NCPC 2023 Onsite Hosted by JU

Problem setter: Muhiminul Islam Osim