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:
import java.util.*;
import java.lang.*;
import java.io.*;

public class B {
	private static FastReader fr;
	private static OutputStream out;
	private static int mod = (int)(1e9+7);
	
	private void solve() {
		int t = fr.nextInt();
		while(t-- > 0) {
			int n = fr.nextInt();
			HashSet<Integer> set = new HashSet<>();
			for(int i=0;i<n;i++) {
				int x = fr.nextInt();
				set.add(x);
			}
			
			int ans = set.size();
			println(ans);
		}
	}

	public static void main(String args[]) throws IOException{
		new B().run();
	}
	
	private ArrayList<Integer> factors(int n, boolean include){
		ArrayList<Integer> factors = new ArrayList<>();
		if(n < 0)
			return factors;
		
		if(include) {
			factors.add(1);
			if(n > 1)
				factors.add(n);
		}
		
		int i = 2;
		for(;i*i<n;i++) {
			if(n % i == 0) {
				factors.add(i);
				factors.add(n / i);
			}
		}
		
		if(i * i == n) {
			factors.add(i);
		}
		
		return factors;
	}
	
	private ArrayList<Integer> PrimeFactors(int n) {
	    ArrayList<Integer> primes = new ArrayList<>();
	 
	    int i = 2;
	    while (i * i <= n) {
	      if (n % i == 0) {
	        primes.add(i);
	 
	        while (n % i == 0) {
	          n /= i;
	        }
	      }
	 
	      i++;
	    }
	 
	    if (n > 1) {
	      primes.add(n);
	    }
	 
	    return primes;
	  }
	
	private boolean isPrime(int n) {
		if(n == 0 || n == 1) {
			return false;
		}
		
		if(n % 2 == 0) {
			return false;
		}
		
		for(int i=3;i*i<=n;i+=2) {
			if(n % i == 0) {
				return false;
			}
		}
		
		return true;
	}

	private ArrayList<Integer> Sieve(int n){
		boolean bool[] = new boolean[n+1];
		Arrays.fill(bool, true);
		bool[0] = bool[1] = false;
		
		for(int i=2;i*i<=n;i++) {
			if(bool[i]) {
				int j = 2;
				while(i*j <= n) {
					bool[i*j] = false;
					j++;
				}
			}
		}
		
		ArrayList<Integer> primes = new ArrayList<>();
		for(int i=2;i<=n;i++) {
			if(bool[i])
				primes.add(i);
		}
		
		return primes;
	}
	
	private HashMap<Integer, Integer> addToHashMap(HashMap<Integer, Integer> map, int arr[]){
		for(int val: arr) {
			if(!map.containsKey(val)) {
				map.put(val, 1);
			}else {
				map.put(val, map.get(val) + 1);
			}
		}
		return map;
	}
	
	private int factorial(int n) {
		long fac = 1;
		for(int i=2;i<=n;i++) {
			fac *= i;
			fac %= mod;
		}
		return (int)(fac % mod);
	}

	private static int pow(int base,int exp){
		if(exp == 0){
			return 1;
		}else if(exp == 1){
			return base;
		}
		int a = pow(base,exp/2);
		a = ((a % mod) * (a % mod)) % mod;
		if(exp % 2 == 1) {
			a = ((a % mod) * (base % mod));
		}
		return a;
	}

	private static int gcd(int a,int b){
		if(a == 0){
			return b;
		}
		
		return gcd(b%a,a);
	}
	
	private static int lcm(int a,int b){
		return (a * b)/gcd(a,b);
	}
	
	private void run() throws IOException{
		fr = new FastReader();
		out = new BufferedOutputStream(System.out);
		solve();
		out.flush();
		out.close();
	}
	
	private static class FastReader{
		private static BufferedReader br; 
		private static StringTokenizer st;
		
		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
			out = new BufferedOutputStream(System.out);
		}
		
		public String next() {
			while (st == null || !st.hasMoreElements()) 
			{ 
				try
				{ 
					st = new StringTokenizer(br.readLine()); 
				} 
				catch (IOException e) 
				{ 
					e.printStackTrace(); 
				} 
			} 
			return st.nextToken();
		}
		
		public String nextLine() { 
			String str = ""; 
			try
			{ 
				str = br.readLine(); 
			} 
			catch (IOException e) 
			{ 
				e.printStackTrace(); 
			} 
			return str; 
		}
		
		public int nextInt() {
			return Integer.parseInt(next());
		}
		
		public long nextLong() {
			return Long.parseLong(next());
		}
		
		public double nextDouble() {
			return Double.parseDouble(next());
		}
		 
		public char[] nextCharArray() {
			return next().toCharArray();
		}
		
		public int[] nextIntArray(int n) {
			int arr[] = new int[n];
			for(int i=0;i<n;i++) {
				arr[i] = nextInt();
			}
			return arr;
		}
		
		public long[] nextLongArray(int n) {
			long arr[] = new long[n];
			for(int i=0;i<n;i++) {
				arr[i] = nextLong();
			}
			return arr;
		}
		
		public String[] nextStringArray(int n) {
			String arr[] = new String[n];
			for(int i=0;i<n;i++) {
				arr[i] = next();
			}
			return arr;
		}
		
	}

	public static void print(Object str) {
        try {
            out.write(str.toString().getBytes());
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
	
	public static void println(Object str) {
        try {
            out.write((str.toString() + "\n").getBytes());
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
	
	public static void println() {
		println("");
	}
	
	public static void printArray(Object str[]){
		for(Object s : str) {
			try {
	            out.write(str.toString().getBytes());
	        } catch (IOException e) {
	            e.printStackTrace();
	        }
		}
	}
}