YouKn0wWho has an integer sequence a_1, a_2, … a_n. Now he will split the sequence a into one or more consecutive subarrays so that each element of a belongs to exactly one subarray. Let k be the number of resulting subarrays, and h_1, h_2, …, h_k be the lengths of the longest increasing subsequences of corresponding subarrays.

For example, if we split [2, 5, 3, 1, 4, 3, 2, 2, 5, 1] into [2, 5, 3, 1, 4], [3, 2, 2, 5], [1], then h = [3, 2, 1].

YouKn0wWho wonders if it is possible to split the sequence a in such a way that the [bitwise XOR](https://en.wikipedia.org/wiki/Bitwise_operation#XOR) of h_1, h_2, …, h_k is equal to 0. You have to tell whether it is possible.

The longest increasing subsequence (LIS) of a sequence b_1, b_2, …, b_m is the longest sequence of valid indices i_1, i_2, …, i_k such that i_1 < i_2 < … < i_k and b_{i_1} < b_{i_2} < … < b_{i_k}. For example, the LIS of [2, 5, 3, 3, 5] is [2, 3, 5], which has length 3.

An array c is a subarray of an array b if c can be obtained from b by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

Input

The first line contains a single integer t (1 ≤ t ≤ 10 000) — the number of test cases.

The first line of each test case contains a single integer n (2 ≤ n ≤ 10^5).

The second line of each test case contains n integers a_1, a_2, …, a_n (1 ≤ a_i ≤ 10^9).

It is guaranteed that the sum of n over all test cases doesn't exceed 3 ⋅ 10^5.

Output

For each test case, print "YES" (without quotes) if it is possible to split into subarrays in the desired way, print "NO" (without quotes) otherwise. You can print each letter in any register (upper or lower).

Example

Input


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


Output


YES
NO
YES
YES

Note

In the first test case, YouKn0wWho can split the sequence in the following way: [1, 3, 4], [2, 2], [1, 5]. This way, the LIS lengths are h = [3, 1, 2], and the bitwise XOR of the LIS lengths is 3 ⊕ 1 ⊕ 2 = 0.

In the second test case, it can be shown that it is impossible to split the sequence into subarrays that will satisfy the condition.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.math.BigInteger;
import java.sql.SQLOutput;
import java.text.DateFormat;
import java.text.Format;
import java.text.ParseException;
import java.text.SimpleDateFormat;
import java.time.LocalDateTime;
import java.util.*;
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;

import static java.util.Comparator.*;
import static java.util.stream.Collectors.*;

public class file {



    private static final Scanner sc = new Scanner(System.in);
    private static String s;
    private static int[] arr;
    private static HashSet<Long> set;
    private static HashMap<Character, Integer> cmap;
    private static Map<Long, Long> Lmap;
    private static Map<Integer, Integer> map;
    private static Stack<Integer> stk;
    private static ArrayList<Integer>[] graph;
    private static boolean[] visited;
    private static ArrayList<Integer> list;
    private static ArrayList<Long> Llist;

    private static final int MOD = 1000000007;

    //find max of array
    private static int findMax(int[] arr) {
        int max = Integer.MIN_VALUE;
        for (int x : arr) {
            max = Math.max(x, max);
        }
        return max;
    }

    // print an array
    private static void printArray(int[] arr) {
        for (int x : arr) {
            System.out.print(x + " ");
        }
        System.out.println();
    }

    //DFS
    private static int dfs(int curr, int prev) {
        int count = 1;
        for (int next : graph[curr]) {
            if (next==prev) continue;
            long new_count = dfs(next, curr);
            Llist.add(new_count* (graph.length - new_count));
            count += new_count;
        }
        return count;
    }

    private static int min_index(int first, int last) {
        int ind = 0, min = Integer.MAX_VALUE;
        for (int i = first; i <= last; i++) {
            if (arr[i] < min) {
                min = arr[i];
                ind = i;
            }
        }
        return ind;
    }

    private static long recurse(int first, int last) {
        int ind = min_index(first, last);
        int min = arr[ind];
        if (first > last) {
            return 0;
        } else {
            return Math.min(last-first + 1, recurse(first, ind - 1) + recurse(ind + 1, last) + min - Math.max(arr[first - 1], arr[last + 1]));
        }
    }

    private static long sum(long y) {
        long sum = 0;
        while (y > 0) {
            sum += (y%10);
            y /= 10;
        }
        return sum;
    }

    private static void popArray(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            arr[i] = sc.nextInt();
        }
    }

    private static int max(int a, int b, int c) {
        return Math.max(max(a,b),c);
    }

    private static int max(int a, int b) {
        return Math.max(a,b);
    }

    private static int min(int a, int b) {
        return Math.min(a,b);
    }

    private static int dfs(int a, ArrayList<Integer>[] G, boolean[] visited, int c, int dest) {
        int ans = 0;
        if (!visited[a]) {
            visited[a] = true;
            for (int k : G[a]) {
                if (k == dest) {
                    return c;
                }
                else if (!visited[k])
                    ans += dfs(k, G, visited, c + 1, dest);
            }
        }
        return ans;
    }

    private static int dbfs(int a, int[] time, ArrayList<Integer>[] Graph) {
        if (time[a] >= 0) return time[a];
        int ans = 1;
        for (int k : Graph[a]) {
            ans += dbfs(k, time, Graph);
        }
        time[a] = ans;
        return ans;
    }



    public static List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> result = new LinkedList<>();
        Arrays.sort(nums);
        boolean []used = new boolean[nums.length];
        dfs(result,nums, new ArrayList<>(),used);
        return result;

    }
    public static void dfs(List<List<Integer>> result , int []nums, List<Integer> current, boolean []used){
        if(current.size() == nums.length){

            result.add(new ArrayList(current));
            return;
        }

        for(int i = 0; i<nums.length;i++){
            if(used[i] == true) continue;
            if(i>0 && nums[i] == nums[i-1] && !used[i-1]) continue;
            current.add( nums[i]);
            used[i] = true;
            dfs(result , nums, current, used);
            current.remove(current.size()-1);
            used[i]  = false;
        }

    }

    public static int findMin(int[] arr) {
        int x = 0, t = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i]  < t) {
                x = i;
                t = arr[i];
            }
        }
        return x;
    }

    public static int[][] restoreMatrix(int[] rowSum, int[] colSum) {
        int[][] mat = new int[rowSum.length][colSum.length];
        while (true) {
            int a = findMin(rowSum);
            int b = findMin(colSum);
            if (rowSum[a] == Integer.MAX_VALUE || colSum[b] == Integer.MAX_VALUE) break;
            mat[a][b] = min(rowSum[a], colSum[b]);
            rowSum[a] -= mat[a][b];
            colSum[b] -= mat[a][b];
            if (rowSum[a] == 0) rowSum[a] = Integer.MAX_VALUE;
            if (colSum[b] == 0) colSum[b] = Integer.MAX_VALUE;
        }
        return mat;
    }


    private static int[] ans;

    private static boolean isPrime(int n)
    {
        if (n <= 1)
            return false;
        if (n <= 3)
            return true;
        if (n % 2 == 0 || n % 3 == 0)
            return false;
        for (int i = 5; i * i <= n; i = i + 6)
            if (n % i == 0 || n % (i + 2) == 0)
                return false;
        return true;
    }

    private static void dfs2(int curr, int val) {
        ans[curr] = val;
        int newVal = val;
        if (newVal > 1) newVal = 1;
        else newVal = 2;
        for (int next : graph[curr]) {
            if (ans[next] > 0) continue;
            dfs2(next, newVal);
        }
    }

    private static void foo(int testCase) {
        //take length of array as input
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++)
            arr[i] = sc.nextInt();
        int iLen = 1;
        for (int i = 1; i < n; i++) {
            if (arr[i] > arr[i - 1]) iLen++;
        }
        if (iLen != n) System.out.println("YES");
        else if (isPrime(iLen)) System.out.println("NO");
        else System.out.println("YES");
    }



    public static void main(String[] args) throws IOException {
        int t = sc.nextInt();
        for (int i = 0; i < t; i++) {
            foo(i + 1);
        }
    }


}