Problem Description

Given a permutation $p_1, p_2, \dots, p_n$ of $1 \sim n$. You can perform several operations.

In each operation you can choose an interval $[l,r]$ and reverse the elements $p_l,p_{l + 1}, \dots,p_r$ to $p_r, p_{r - 1}, \dots,p_l$, the weight of this operation is $r-l+1$.

You can perform any number of operations, and your goal is to make $p_i=i$ at last.

Please calculate the minimal and maximal XOR sum of the weight of all the operations.

Input

The input consists of multiple test cases. The first line contains a single integer $T$ ($1 \le T \le 2 \times 10 ^ 5$) - the number of test cases. Description of the test cases follows.

The first line of each test case contains one integer $n$ ($1\leq n\leq 10^5$).

The second line contains $n$ integers $p_1, p_2, \dots, p_n$.

It's guaranteed that $\sum n \leq 6\times10^5$.

Output

For each test case, print two integers - the minimal and maximal XOR sum of the weight of all the operations.

3
3
1 3 2
3
3 1 2
6
1 2 5 6 3 4

2 3
0 1
0 5