2018-2019 ICPC, NEERC, Southern Subregional Contest (Online Mirror, ACM-ICPC Rules, Teams Preferred) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
J. Streets and Avenues in Berhattan

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputBerhattan 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.

Recently, the government has changed in Berland. The new government wants to name all avenues and all streets after heroes of revolution.

The 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.

The 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 inconvenient. Hence only the first letter of each name matters.

Given first letters of $$$k$$$ names, find $$$C$$$ — minimal possible number of inconvenient crossroads in Berhattan after the naming process.

Input

Input 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.

The 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's list, respectively.

The 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's list.

It's 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$$$.

Output

For each test case print single number $$$C$$$ in the separate line — minimal possible number of inconvenient crossroads in Berhattan after the naming process.

Examples

Input

2

2 3 9

EEZZEEZZZ

2 7 9

EEZZEEZZZ

Output

0

4

Input

2

4 4 8

CZBBCZBC

1 1 4

TTCT

Output

1

0

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/07/2023 01:31:26 (k3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|