{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"Given a set of **n** DNA samples, where each sample is a string containing characters from **{A, C, G, T}**, we are trying to find a subset of samples in the set, where the length of the longest common prefix multiplied by the number of samples in that subset is maximum.\n\nTo be specific, let the samples be: \n\n1. ACGT\n2. ACGTGCGT\n3. ACCGTGC\n4. ACGCCGT\n\nIf we take the subset **{ACGT}** then the result is **4 (4 * 1)**, if we take **{ACGT, ACGTGCGT, ACGCCGT}** then the result is **3 \\* 3 \u003d 9** (since ACG is the common prefix), if we take **{ACGT, ACGTGCGT, ACCGTGC, ACGCCGT}** then the result is **2 \\* 4 \u003d 8**.\n\nNow your task is to report the maximum result we can get from the samples.\n"}},{"title":"Input","value":{"format":"MD","content":"Input starts with an integer **T (\u0026le; 10)**, denoting the number of test cases.\n\nEach case starts with a line containing an integer **n (1 \u0026le; n \u0026le; 50000)** denoting the number of DNA samples. Each of the next **n** lines contains a non empty string whose length is not greater than **50**. And the strings contain characters from **{A, C, G, T}**."}},{"title":"Output","value":{"format":"MD","content":"For each case, print the case number and the maximum result that can be obtained."}},{"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\u003e3\n4\nACGT\nACGTGCGT\nACCGTGC\nACGCCGT\n3\nCGCGCGCGCGCGCCCCGCCCGCGC\nCGCGCGCGCGCGCCCCGCCCGCAC\nCGCGCGCGCGCGCCCCGCCCGCTC\n2\nCGCGCCGCGCGCGCGCGCGC\nGGCGCCGCGCGCGCGCGCTC\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase 1: 9\nCase 2: 66\nCase 3: 20\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"MD","content":"Dataset is huge. Use faster I/O methods."}}]}