A. XXXXX

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

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

An array aa is a subarray of an array bb if aa can be obtained from bb 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 tt (1≤t≤5)(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 nn and xx (1≤n≤1051≤n≤105, 1≤x≤1041≤x≤104) — the number of elements in the array aa and the number that Ehab hates.

The second line contains nn space-separated integers a1a1, a2a2, ……, anan (0≤ai≤1040≤ai≤104) — the elements of the array aa.

Output

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

Example

input

Copy

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

output

Copy

2
3
-1

Note

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

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

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

解题说明：此题是一道数学题，为了确保不被y整除，先按余数进行求和，所有的数都是b的倍数，那无论a的那个子区间的和都是b的倍数。a的总和不是b的倍数，那答案就是整个数组的长度。a的总和是b的倍数，则从左往右找第一个不是b的倍数的数的下标x，从右往左找第一个不是b的倍数的数的下标y。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>

using namespace std;

int main() 
{
	int t, a[100000], b[100000], y, i, r, l, n;
	scanf("%d", &t);
	while (t--) 
	{
		scanf("%d", &n);
		scanf("%d", &y);
		for (i = 1; i <= n; i++) 
		{
			scanf("%d", &a[i]);
			a[i] = a[i] % y;
			b[i] = a[i];
		}
		a[0] = 0;
		for (i = 1; i <= n; i++) 
		{
			a[i] += a[i - 1];
		}
		if (a[n] % y != 0) 
		{
			printf("%d\n", n);
		}
		else 
		{
			r = n;
			while (r >= 1 && b[r] % y == 0) 
			{
				r--;
			}
			r--;
			l = 1;
			while (l <= n && b[l] % y == 0) 
			{
				l++;
			}
			if (n - l > r) 
			{
				printf("%d\n", n - l);
			}
			else 
			{
				printf("%d\n", r);
			}
		}
	}
	return 0;
}