{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"Optimus Mobiles produces mobile phones that support SMS messages. The Mobiles have a keypad of 12 keys, numbered 1 to 12. There is a character string assigned to each key. To type in the n-th character in the character string of a particular key, one should press the key n times. Optimus Mobiles wishes to solve the problem of assigning character strings to the keys such that for typing a random text out of a dictionary of common words, the average typing effort (i.e. the average number of keystrokes) is minimal. \r\u003cbr\u003e\u003ccenter\u003e\u003cimg src\u003d\"CDN_BASE_URL/18fbf6166670dec51f5a5ef7a7f6badb?v\u003d1715572241\"\u003e\r\u003cbr\u003eFigure 1\u003c/center\u003e\r\u003cbr\u003eTo be more precise, consider a set of characters {a, b, c,..., z, +, *, /, ?} printed on a label tape as in Fig. 2. We want to cut the tape into 12 pieces each containing one or more characters. The 12 labels are numbered 1 to 12 from left to right and will be assigned to the keypad keys in that order. \r\u003cbr\u003e\u003ccenter\u003e\u003cimg src\u003d\"CDN_BASE_URL/29fc7fdf3ab8396a058c4865d417dc02?v\u003d1715572241\"\u003e\r\u003cbr\u003eFigure 2\u003c/center\u003e\r\u003cbr\u003eYou are to write a program to find the 11 cutting positions for a given dictionary of common words. The cutting positions should minimize the average number of keystrokes over all common words in the dictionary. Your output should be a string of 11 characters, where character i in this string is the first character of the (i+1)\u003csup\u003eth\u003c/sup\u003e label."}},{"title":"Input","value":{"format":"HTML","content":"The first line contains a single integer t (1 \u0026lt;\u003d t \u0026lt;\u003d 10), the number of test cases. Each test case starts with a line, containing an integer M (1 \u0026lt;\u003d M \u0026lt;\u003d 10000), the number of common words in the test case. In each M subsequent line, there is a common word. Each common word contains at most 30 characters from the alphabet {a, b, c,..., z, +, *, /, ?}."}},{"title":"Output","value":{"format":"HTML","content":"The output contains one line per test case containing an optimal cut string. Obviously, there may be more than a single optimal cut string, so print the optimal cut string which is the smallest one in lexicographic order."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n2\r\nhi\r\nok\r\n5\r\nhello\r\nbye\r\nhow\r\nwhen\r\nwho\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003ebcdefghijko\r\nbcdefhlnowy\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}