C. Hasan and his lazy students
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Hasan is teaching Dynamic Programming to his students at NCD. However, he feels they aren't studying what he is giving them, so he decided to test them on the NCDPC. He will give them an array of length $$$N$$$, and they must tell him how many Longest Increasing Subsequences are in the array.

For example, if the array is ($$$1$$$ $$$2$$$ $$$1$$$ $$$4$$$ $$$3$$$). The LIS's length is $$$3$$$, and it could be ($$$1$$$ $$$2$$$ $$$4$$$) or ($$$1$$$ $$$2$$$ $$$3$$$), so the answer is $$$2$$$. Note that you can't choose ($$$1$$$ $$$1$$$ $$$3$$$) because it must be a strictly increasing subsequence, and you can't choose ($$$1$$$ $$$2$$$ $$$3$$$ $$$4$$$) because you can't change the order of a subsequence.

Input

First line of the input will be $$$T$$$, number of test cases.

Each test case starts with $$$N$$$, the size of the array, next line contain $$$N$$$ space separated integers, the array.

$$$1\le N \le 1000, 1 \le A_i \le 10^6 $$$

Output

For each test case print one line, the length of the LIS and the number of LISes. As this number may be very large, print it module $$$10^9+7$$$

Example
Input
3
5
1 3 2 3 1
3
1 2 3
7
1 5 6 2 1 4 1
Output
3 1
3 1
3 2