Counting Special Sub-Cubes

Given an cube, let (where ) denote the value stored in cell .

A sub-cube (where ) of an cube is considered to be special if the maximum value stored in any cell in the sub-cube is equal to .

For each in the inclusive range , calculate the number of special sub-cubes. Then print each as a single line of space-separated integers (i.e., ).

Input Format

The first line contains an integer, , denoting the number of queries. The subsequent lines describe each query over two lines:

The first line contains an integer, , denoting the side length of the initial cube.
The second line contains space-separated integers describing an array of integers in the form . The integer in some cell is calculated using the formula .

Constraints

Output Format

For each query, print space-separated integers where the integer denotes the number of special sub-cubes for .

Sample Input

2
2
2 1 1 1 1 1 1 1
2
1 1 1 1 2 1 1 2

Sample Output

7 1
6 1

Explanation

We must perform the following queries:

We have a cube of size and must calculate the number of special sub-cubes for the following values of :
- : There are sub-cubes of size and seven of them have a maximum value of written inside them. So, for , the answer is .
- : There is only one sub-cube of size and the maximum number written inside it is . So, for , the answer is .
We then print the respective values for each as a single line of space-separated integers (i.e., 7 1).
We have a cube of size and must calculate the number of special sub-cubes for the following values of :
- : There are sub-cubes of size and six of them have a maximum value of written inside them. So, for , the answer is .
- : There is only one sub-cube of size and the maximum number written inside it is . So, for , the answer is .
We then print the respective values for each as a single line of space-separated integers (i.e., 6 1).