M. Minimal and Maximal XOR Sum

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.

Sample Input

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

Sample Output

2 3
0 1
0 5

Source

2023“钉耙编程”中国大学生算法设计超级联赛（7）