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
- where
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).