{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eBerhattan is the capital of Berland. There are $$$n$$$ streets running parallel in the east-west direction (horizontally), and there are $$$m$$$ avenues running parallel in the south-north direction (vertically). Each street intersects with each avenue, forming a crossroad. So in total there are $$$n \\cdot m$$$ crossroads in Berhattan.\u003c/p\u003e\u003cp\u003eRecently, the government has changed in Berland. The new government wants to name all avenues and all streets after heroes of revolution.\u003c/p\u003e\u003cp\u003eThe special committee prepared the list of $$$k$$$ names. Only these names can be used as new names for streets and avenues. Each name can be used at most once.\u003c/p\u003e\u003cp\u003eThe members of committee want to name streets and avenues in the way that minimizes inconvenience for residents. They believe that if street and avenue names start with the same letter, then their crossroad will be \u003cspan class\u003d\"tex-font-style-it\"\u003einconvenient\u003c/span\u003e. Hence only the first letter of each name matters.\u003c/p\u003e\u003cp\u003eGiven first letters of $$$k$$$ names, find $$$C$$$ — minimal possible number of inconvenient crossroads in Berhattan after the naming process.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eInput contains one or several test cases to process. The first line contains $$$t$$$ ($$$1 \\le t \\le 30000$$$) — the number of test cases. Solve test cases separately, test cases are completely independent and do not affect each other.\u003c/p\u003e\u003cp\u003eThe description of $$$t$$$ test cases follows. Each test case starts with line with space-separated numbers $$$n, m, k$$$ ($$$1 \\le n,m \\le 30000$$$; $$$n+m \\le k \\le 2\\cdot10^5$$$) — the number of streets, number of avenues and the number of names in the committee\u0027s list, respectively.\u003c/p\u003e\u003cp\u003eThe the second line of each test case contains a string of $$$k$$$ uppercase English letters. $$$i$$$-th letter of the string is the first letter of $$$i$$$-th name from the committee\u0027s list. \u003c/p\u003e\u003cp\u003eIt\u0027s guaranteed that the sum of numbers $$$n$$$ from all test cases is not greater than $$$30000$$$. Similarly, the sum of numbers $$$m$$$ from all test cases is not greater than $$$30000$$$. The sum of numbers $$$k$$$ from all test cases is not greater than $$$2\\cdot10^5$$$.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor each test case print single number $$$C$$$ in the separate line — minimal possible number of inconvenient crossroads in Berhattan after the naming process.\u003c/p\u003e"}},{"title":"Examples","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\n2 3 9\nEEZZEEZZZ\n2 7 9\nEEZZEEZZZ\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0\n4\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","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\n4 4 8\nCZBBCZBC\n1 1 4\nTTCT\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\n0\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}