Problem

Sarah has a basket of fruits, each represented by a lowercase English letter. She wants to know how many different types of fruits she has in her basket. Additionally, she wants to know how many unique ways she can pick a subset of these fruits such that the subset contains exactly k distinct fruit types.

Your task is to determine the number of unique subsets of fruits that contain exactly k distinct types. Two subsets are considered the same if they contain the same multiset of fruits (order does not matter).

Input

The first line contains an integer T, the number of test cases. For each test case:

• An integer k, representing the desired number of distinct fruit types.
• A string S, where each character represents a fruit type in Sarah's basket.

Output

For each test case, print a single integer — the number of unique subsets containing exactly k distinct types.