Problem: Ehab loves number theory, but for some reason he hates the number x. Given an array a, find the length of its longest subarray such that the sum of its elements isn't divisible by x, or determine that such subarray doesn't exist.

An array a is a subarray of an array b if a 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 an integer t (1 ≤ t ≤ 5) — the number of test cases you need to solve. The description of the test cases follows.

The first line of each test case contains 2 integers n and x (1 ≤ n ≤ 10^5, 1 ≤ x ≤ 10^4) — the number of elements in the array a and the number that Ehab hates.

The second line contains n space-separated integers a_1, a_2, …, a_{n} (0 ≤ a_i ≤ 10^4) — the elements of the array a.

Output

For each testcase, print the length of the longest subarray whose sum isn't divisible by x. If there's no such subarray, print -1.

Example

Input


3
3 3
1 2 3
3 4
1 2 3
2 2
0 6


Output


2
3
-1

Note

In the first test case, the subarray [2,3] has sum of elements 5, which isn't divisible by 3.

In the second test case, the sum of elements of the whole array is 6, which isn't divisible by 4.

In the third test case, all subarrays have an even sum, so the answer is -1.

Solution (in JAVA):

Solution:
//package com.company;

//-------------------------------------------># DEVIL CODER # -----------------------------------------------------------------------------------------------------------------------------------------------------------------------------




import java.math.*;
import javax.swing.*;
import java.lang.reflect.Array;
import java.util.*;
import java.lang.*;
import java.io.*;
import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.StringTokenizer;
//-------------------Main function ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
public class Main {
    //---------------Reader class for Fast Input------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
    static class Reader {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;


        public Reader() {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }


        public Reader(String file_name) throws IOException {
            din = new DataInputStream(new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        // ----------------------Down-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
        public String readLine() throws IOException {
            byte[] buf = new byte[64]; // line length
            int cnt = 0, c;
            while ((c = read()) != -1) {
                if (c == '\n')
                    break;
                buf[cnt++] = (byte) c;
            }
            return new String(buf, 0, cnt);
        }

        // Down---------------->>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
        public int nextInt() throws IOException {
            int ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');

            if (neg)
                return -ret;
            return ret;
        }

        // Down---------------->>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
        public long nextLong() throws IOException {
            long ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            }
            while ((c = read()) >= '0' && c <= '9');
            if (neg)
                return -ret;
            return ret;
        }

        // Down---------------->>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
        public double nextDouble() throws IOException {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();

            do {
                ret = ret * 10 + c - '0';
            }
            while ((c = read()) >= '0' && c <= '9');

            if (c == '.') {
                while ((c = read()) >= '0' && c <= '9') {
                    ret += (c - '0') / (div *= 10);
                }
            }

            if (neg)
                return -ret;
            return ret;
        }

        // Down---------------->>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>---------------------------------------------------------------------------------------->>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
        private void fillBuffer() throws IOException {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        }

        // Down---------------->>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
        private byte read() throws IOException {
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }

        // Down---------------->>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
        public void close() throws IOException {
            if (din == null)
                return;
            din.close();
        }
    }

    // ---------------->>>>>>>>>seieve of erathoshenes ------------------------------------------------------------------->>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
    static ArrayList<Integer> sieveOfEratosthenes(int n) {
        boolean prime[] = new boolean[n + 1];
        for (int i = 0; i < n; i++)
            prime[i] = true;

        for (int p = 2; p * p <= n; p++) {
            // If prime[p] is not changed, then it is a prime
            if (prime[p] == true) {
                // Update all multiples of p
                for (int i = p * p; i <= n; i += p)
                    prime[i] = false;
            }
        }
        ArrayList<Integer> l = new ArrayList<>();
        for (int i = 2; i <= n; i++) {
            if (prime[i] == true)
                l.add(i);
        }
        return l;
    }

    // ---------------------------------GCD>>>>>>>>>>>>>>>>>>>>>>>>>>>>-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
    static int gcd(int a, int b) {
        if (a == 0)
            return b;
        return gcd(b % a, a);
    }

    // ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
    static ArrayList<Integer> factor(int n) {
        ArrayList<Integer> l = new ArrayList<>();

        for (int i = n; i <= 1e5; i++) {
            if (i % n == 0)
                l.add(n);
        }
        return l;
    }


    // ------------------------------------------------------------------------------------------------------->>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
//map code
      /*
                                                 if (h.containsKey(A[i]))
                                                   h.put(A[i], h.get(A[i]) + 1);
                                               else
                                                   h.put(A[i], 1);

                                         ArrayList<Integer> l = new ArrayList<>();
                                          for(Map.Entry mp:h.entrySet())
                                            {
                                                if((int)mp.getValue()>1)
                                                {
                                                    sum+=(int)mp.getValue();
                                                }
                                                else
                                                {
                                                  l.add((int)mp.getKey());
                                                }
                                            }
                                            Collections.sort(l);
                                            for(int i=0;i<l.size();i++)
                                            {
                                                int x=l.get(i);
                                                if(sum>=x)
                                                    sum++;
                                            }*/


    //---------------->>>>>>>>>>>>>>>>>>>><<<<<<<<<<<<<<<<<<<<>>>>>>>>>>>>>>>>>><<<<<<<<<<<<<<<<<<<<<<<<>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
// ---------------->>>>>>>>>Coding begins ------------------------------------------------------------------->>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
    public static int maxSum(int arr[], int n, int k)
    {
        // k must be greater
        if (n < k)
        {
            System.out.println("Invalid");
            return -1;
        }

        // Compute sum of first window of size k
        int res = 0;
        for (int i=0; i<k; i++)
            res += arr[i];

        // Compute sums of remaining windows by
        // removing first element of previous
        // window and adding last element of
        // current window.
        int curr_sum = res;
        for (int i=k; i<n; i++)
        {
            curr_sum += arr[i] - arr[i-k];
            res = Math.max(res, curr_sum);
        }

        return res;
    }
 ///------------------------->>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
    static class customer implements Comparable<customer>
 {
     int start;
     int end;
     int pre;
     customer(int start,int end,int pre) {
         this.start = start;
         this.end = end;
         this.pre = pre;
     }
     public int compareTo(customer a)
     {
         return end-a.end;
     }

 }


//------------------------------------------------------------------------------------------------------->>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
    //---------------->>>>>>>>>>>>>>>>>>>><<<<<<<<<<<<<<<<<<<<>>>>>>>>>>>>>>>>>><<<<<<<<<<<<<<<<<<<<<<<<>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
//----<<<<<<<<<------------>>>>>>>>>>>>>### $$$solve ### devil_coder$$$#######<<<<<<<------------------>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
















//----------------Main function----------------------------------->>>>>>>>>>>>>>>>>>>>>>>>>>>>>------------------->>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>-------------------------------------------->>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>


    public static void main(String[] args) throws java.lang.Exception
    {

        Reader sc = new Reader();
        //BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        //int t = Integer.parseInt(br.readLine());
        StringBuffer sb = new StringBuffer();

        int max=10000000;
        int t=sc.nextInt();
        while(t-->0) {

            //HashSet<Integer> hs=new HashSet<>();

            int n = sc.nextInt();
            int sol=0;
            long x=sc.nextInt();
            int A[]=new int[n];
            int sum=0;
            for(int i=0;i<n;i++)
            {
                A[i]=sc.nextInt();
                sum+=A[i];
            }
            int s=sum;
            if(sum%x!=0)
                sol=n;
            else
            {
                for(int i=0;i<n;i++)
                {
                    sum=sum-A[i];
                    if(sum%x!=0) {
                        sol = n - (i + 1);
                        break;
                    }
                }
            }
            if(sum==0)
                sol=-1;

            int ans=0;

            if(s%x!=0)
                ans=n;
            else
            {
                for(int i=0;i<n;i++)
                {
                    s=s-A[n-i-1];
                    if(s%x!=0)
                    {
                        ans=n-(i+1);
                        break;
                    }
                }
            }

            if(s==0)
                ans=-1;

            int fi=Math.max(sol,ans);







            sb.append(fi + "\n");
            //System.out.println(sum);
        }
        System.out.println(sb);


    }
}