Count Distinct Characters in Substrings

This problem requires you to compute the number of distinct characters in every substring of a given string. Specifically, for a string \(S\) of length \(N\), you need to construct an \(N \times N\) matrix \(M\) where the element \(M[i][j]\) (with 0-indexing) is defined as:

\[ M[i][j] = \left| \{ S[k] : i \le k \le j \} \right| \]

That is, each cell holds the count of distinct characters in the substring \(S[i \ldots j]\). You are given multiple test cases. For each test case, you will be provided with an integer \(N\) and a string \(S\) of length \(N\). Your task is to output the corresponding matrix for each test case.

inputFormat

The first line of input contains a single integer \(T\) representing the number of test cases. Each test case consists of two lines:

• The first line contains an integer \(N\), the length of the string.
• The second line contains the string \(S\) which consists of lowercase letters.

outputFormat

For each test case, output the \(N \times N\) matrix. Each of the following \(N\) lines should contain \(N\) space-separated integers representing one row of the matrix. Print an empty line after each test case.

## sample

1
3
abc

1 2 3
0 1 2
0 0 1

</p>