You are given a list of numbers, which contains the numbers 1,2,\dots,n in some order.

Determine whether it is possible to sort the numbers from smallest to largest by repeating the following operation zero or more times: choose two separate pairs of adjacent numbers, and switch these pairs with each other.

For example, the list [2,3,5,1,4] can be sorted using two operations: [\underline{2,3},5,\underline{1,4}] \rightarrow [1,\underline{4,5},\underline{2,3}] \rightarrow [1,2,3,4,5].

Input

The first line of input consists of an integer t: the number of test cases.

The first line of each test contains the integer n and the second line describes the contents of the list.

Output

For each test, print YES if the list can be sorted, NO otherwise.

Example

Input:

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

Output:

YES
YES
NO

Subtask 1 (36 points)

• 1 \le t \le 1000
• 1 \le n \le 8

Subtask 2 (64 points)

• 1 \le t \le 1000
• 1 \le n \le 100