Raon and Ice Cream

Raon was on her way to home when she saw the shop famous for selling very delicious ice cream. This shop sells ice cream with 26 different flavors (from 'A' to 'Z'). Raon decided to buy N scoops of ice cream and take them home; of course, each scoop has its own flavor. Interestingly, the ice cream she bought is arranged sequentially by the scoops such that it resembles a long bar, e.g., ABBBABBBAABB is a 12 scoops ice cream with the first scoop's flavor is A, the second scoop's flavor is B, the third scoop's flavor is B, and so on.

After Raon arrived at her home, she decided to share the ice cream with all of her neighbors. Raon cannot rearrange the ice cream but she can cut them in between scoops into several parts. Raon wants to be as fair as possible, thus, she requires each part to have the same number of scoops; moreover, each part should have the same number of flavors (order does not matter) with any other part. Then she will give each neighbor exactly one part. Note that there should be no remaining scoops after she distributed all the parts.

Raon wonders, what is the maximum possible number of parts can be made from the ice cream she just bought?


Input begins with an integer: T (1 ≤ T ≤ 20) denoting the number of cases.

Each case contains the following input block: Each case begins with an integer: N (1 ≤ N ≤ 500,000) denoting the number of scoops the ice cream Raon bought. The next line contains a string of length N denoting the ice cream's scoops in order. The string contains only uppercase alphabet character ('A' to 'Z') and each represents a different flavor.

The sum of all N in the input is no larger than 1,000,000.


For each case, output in a line "Case #X: Y" where X is the case number (starts from 1) and Y is the output for the respective case.


inputExample #1
Case #1: 4
Case #2: 1

Case 1: There are several possible cuts can be made:

  • Make it into 1 part: ABBBABBBAABB, where each part contains 4A and 8B.
  • Make it into 2 parts: ABBBAB-BBAABB, where each part contains 2A and 4B.
  • Make it into 4 parts: ABB-BAB-BBA-ABB, where each part contains 1A and 2B.
The best we can do is to make it into 4 parts.

Case 2: All scoops have different flavor; we cannot cut the ice cream and make them to have an equal number of flavor.

End of Problem