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.
import java.util.*;
import java.io.*;
import java.math.*;
public class Main{
static FastScanner c;
static PrintWriter pw;
static void pn(Object o){pw.println(o);}
static void p(Object o){pw.print(o);}
static Random rand = new Random();
// eferences
// IBIG = 1e9 + 7
// IMAX ~= 2e9
// LMAX ~= 9e18
// constants
static final int IBIG = 1000000007;
static final int IMAX = 2147483647;
static final int IMIN = -2147483648;
static final long LMAX = 9223372036854775807L;
static final long LMIN = -9223372036854775808L;
// math util
static int minof(int a, int b, int c) {return min(a, min(b, c));}
static int minof(int... x) {if (x.length == 1) return x[0]; if (x.length == 2) return min(x[0], x[1]); if (x.length == 3) return min(x[0], min(x[1], x[2])); int min = x[0]; for (int i = 1; i < x.length; ++i) if (x[i] < min) min = x[i]; return min;}
static long minof(long a, long b, long c) {return min(a, min(b, c));}
static long minof(long... x) {if (x.length == 1) return x[0]; if (x.length == 2) return min(x[0], x[1]); if (x.length == 3) return min(x[0], min(x[1], x[2])); long min = x[0]; for (int i = 1; i < x.length; ++i) if (x[i] < min) min = x[i]; return min;}
static int maxof(int a, int b, int c) {return max(a, max(b, c));}
static int maxof(int... x) {if (x.length == 1) return x[0]; if (x.length == 2) return max(x[0], x[1]); if (x.length == 3) return max(x[0], max(x[1], x[2])); int max = x[0]; for (int i = 1; i < x.length; ++i) if (x[i] > max) max = x[i]; return max;}
static long maxof(long a, long b, long c) {return max(a, max(b, c));}
static long maxof(long... x) {if (x.length == 1) return x[0]; if (x.length == 2) return max(x[0], x[1]); if (x.length == 3) return max(x[0], max(x[1], x[2])); long max = x[0]; for (int i = 1; i < x.length; ++i) if (x[i] > max) max = x[i]; return max;}
static int powi(int a, int b) {if (a == 0) return 0; int ans = 1; while (b > 0) {if ((b & 1) > 0) ans *= a; a *= a; b >>= 1;} return ans;}
static long powl(long a, int b) {if (a == 0) return 0; long ans = 1; while (b > 0) {if ((b & 1) > 0) ans *= a; a *= a; b >>= 1;} return ans;}
static int fli(double d) {return (int) d;}
static int cei(double d) {return (int) Math.ceil(d);}
static long fll(double d) {return (long) d;}
static long cel(double d) {return (long) Math.ceil(d);}
static int gcf(int a, int b) {return b == 0 ? a : gcf(b, a % b);}
static long gcf(long a, long b) {return b == 0 ? a : gcf(b, a % b);}
static int lcm(int a, int b) {return a * b / gcf(a, b);}
static long lcm(long a, long b) {return a * b / gcf(a, b);}
static int randInt(int min, int max) {return rand.nextInt(max - min + 1) + min;}
static long mix(long x) {x += 0x9e3779b97f4a7c15L; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9L; x = (x ^ (x >> 27)) * 0x94d049bb133111ebL; return x ^ (x >> 31);}
// array util
static void reverse(int[] a) {for (int i = 0, n = a.length, half = n / 2; i < half; ++i) {int swap = a[i]; a[i] = a[n - i - 1]; a[n - i - 1] = swap;}}
static void reverse(int [] a, int n, int k)
{
    if (k > n)
    {
        System.out.println( "Invalid k");
        return;
    }
 
    // One by one reverse first
    // and last elements of a[0..k-1]
    for (int i = 0; i < k / 2; i++)
    {
        int tempswap = a[i];
            a[i] = a[k - i - 1];
            a[k - i - 1] = tempswap;            
    }
}
static void reverse(long[] a) {for (int i = 0, n = a.length, half = n / 2; i < half; ++i) {long swap = a[i]; a[i] = a[n - i - 1]; a[n - i - 1] = swap;}}
static void reverse(double[] a) {for (int i = 0, n = a.length, half = n / 2; i < half; ++i) {double swap = a[i]; a[i] = a[n - i - 1]; a[n - i - 1] = swap;}}
static void reverse(char[] a) {for (int i = 0, n = a.length, half = n / 2; i < half; ++i) {char swap = a[i]; a[i] = a[n - i - 1]; a[n - i - 1] = swap;}}
static void shuffle(int[] a) {int n = a.length - 1; for (int i = 0; i < n; ++i) {int ind = randInt(i, n); int swap = a[i]; a[i] = a[ind]; a[ind] = swap;}}
static void shuffle(long[] a) {int n = a.length - 1; for (int i = 0; i < n; ++i) {int ind = randInt(i, n); long swap = a[i]; a[i] = a[ind]; a[ind] = swap;}}
static void shuffle(double[] a) {int n = a.length - 1; for (int i = 0; i < n; ++i) {int ind = randInt(i, n); double swap = a[i]; a[i] = a[ind]; a[ind] = swap;}}
static void sort(int[] a) {shuffle(a); Arrays.parallelSort(a);}
static void rsort(long[] a) {shuffle(a); Arrays.parallelSort(a);}
static void rsort(double[] a) {shuffle(a); Arrays.parallelSort(a);}
static int[] copy(int[] a) {int[] ans = new int[a.length]; for (int i = 0; i < a.length; ++i) ans[i] = a[i]; return ans;}
static long[] copy(long[] a) {long[] ans = new long[a.length]; for (int i = 0; i < a.length; ++i) ans[i] = a[i]; return ans;}
static double[] copy(double[] a) {double[] ans = new double[a.length]; for (int i = 0; i < a.length; ++i) ans[i] = a[i]; return ans;}
static char[] copy(char[] a) {char[] ans = new char[a.length]; for (int i = 0; i < a.length; ++i) ans[i] = a[i]; return ans;}
// graph util
static List<List<Integer>> g(int n) {List<List<Integer>> g = new ArrayList<>(); for (int i = 0; i < n; ++i) g.add(new ArrayList<>()); return g;}
static List<Set<Integer>> sg(int n) {List<Set<Integer>> g = new ArrayList<>(); for (int i = 0; i < n; ++i) g.add(new HashSet<>()); return g;}
static void c(List<? extends Collection<Integer>> g, int u, int v) {g.get(u).add(v); g.get(v).add(u);}
static void cto(List<? extends Collection<Integer>> g, int u, int v) {g.get(u).add(v);}
static void dc(List<? extends Collection<Integer>> g, int u, int v) {g.get(u).remove(v); g.get(v).remove(u);}
static void dcto(List<? extends Collection<Integer>> g, int u, int v) {g.get(u).remove(v);}
// input
// static void r() throws IOException {input = new StringTokenizer(rline());}
// static int ri() throws IOException {return Integer.parseInt(rline());}
// static long rl() throws IOException {return Long.parseLong(rline());}
// static double rd() throws IOException {return Double.parseDouble(rline());}
// static int[] ria(int n) throws IOException {int[] a = new int[n]; r(); for (int i = 0; i < n; ++i) a[i] = ni(); return a;}
// static int[] riam1(int n) throws IOException {int[] a = new int[n]; r(); for (int i = 0; i < n; ++i) a[i] = ni() - 1; return a;}
// static long[] rla(int n) throws IOException {long[] a = new long[n]; r(); for (int i = 0; i < n; ++i) a[i] = nl(); return a;}
// static double[] rda(int n) throws IOException {double[] a = new double[n]; r(); for (int i = 0; i < n; ++i) a[i] = nd(); return a;}
// static char[] rcha() throws IOException {return rline().toCharArray();}
// static String rline() throws IOException {return br.readLine();}
// static String n() {return input.nextToken();}
// static int rni() throws IOException {r(); return ni();}
// static int ni() {return Integer.parseInt(n());}
// static long rnl() throws IOException {r(); return nl();}
// static long nl() {return Long.parseLong(n());}
// static double rnd() throws IOException {r(); return nd();}
// // static double nd() {return Double.parseDouble(n());}
// static List<List<Integer>> rg(int n, int m) throws IOException {List<List<Integer>> g = g(n); for (int i = 0; i < m; ++i) c(g, rni() - 1, ni() - 1); return g;}
// static void rg(List<List<Integer>> g, int m) throws IOException {for (int i = 0; i < m; ++i) c(g, rni() - 1, ni() - 1);}
// static List<List<Integer>> rdg(int n, int m) throws IOException {List<List<Integer>> g = g(n); for (int i = 0; i < m; ++i) cto(g, rni() - 1, ni() - 1); return g;}
// static void rdg(List<List<Integer>> g, int m) throws IOException {for (int i = 0; i < m; ++i) cto(g, rni() - 1, ni() - 1);}
// static List<Set<Integer>> rsg(int n, int m) throws IOException {List<Set<Integer>> g = sg(n); for (int i = 0; i < m; ++i) c(g, rni() - 1, ni() - 1); return g;}
// static void rsg(List<Set<Integer>> g, int m) throws IOException {for (int i = 0; i < m; ++i) c(g, rni() - 1, ni() - 1);}
// static List<Set<Integer>> rdsg(int n, int m) throws IOException {List<Set<Integer>> g = sg(n); for (int i = 0; i < m; ++i) cto(g, rni() - 1, ni() - 1); return g;}
// static void rdsg(List<Set<Integer>> g, int m) throws IOException {for (int i = 0; i < m; ++i) cto(g, rni() - 1, ni() - 1);}
// output
static void pr(int i) {pw.print(i);}
static void prln(int i) {pw.println(i);}
static void pr(long l) {pw.print(l);}
static void prln(long l) {pw.println(l);}
static void pr(double d) {pw.print(d);}
static void prln(double d) {pw.println(d);}
static void pr(char c) {pw.print(c);}
static void prln(char c) {pw.println(c);}
static void pr(char[] s) {pw.print(new String(s));}
static void prln(char[] s) {pw.println(new String(s));}
static void pr(String s) {pw.print(s);}
static void prln(String s) {pw.println(s);}
static void pr(Object o) {pw.print(o);}
static void prln(Object o) {pw.println(o);}
static void prln() {pw.println();}
static void pryes() {prln("yes");}
static void pry() {prln("Yes");}
static void pY() {prln("YES");}
static void prno() {prln("no");}
static void prn() {prln("No");}
static void pN() {prln("NO");}
static void pryesno(boolean b) {prln(b ? "yes" : "no");};
static void pryn(boolean b) {prln(b ? "Yes" : "No");}
static void prYN(boolean b) {prln(b ? "YES" : "NO");}
static void prln(int... a) {for (int i = 0, len = a.length - 1; i < len; pr(a[i]), pr(' '), ++i); if (a.length > 0) prln(a[a.length - 1]); else prln();}
static void prln(long... a) {for (int i = 0, len = a.length - 1; i < len; pr(a[i]), pr(' '), ++i); if (a.length > 0) prln(a[a.length - 1]); else prln();}
static void prln(double... a) {for (int i = 0, len = a.length - 1; i < len; pr(a[i]), pr(' '), ++i); if (a.length > 0) prln(a[a.length - 1]); else prln();}
static <T> void prln(Collection<T> c) {int n = c.size() - 1; Iterator<T> iter = c.iterator(); for (int i = 0; i < n; pr(iter.next()), pr(' '), ++i); if (n >= 0) prln(iter.next()); else prln();}
static void h() {prln("hlfd"); flush();}
static void flush() {pw.flush();}
static void close() {pw.close();}
static boolean arr[] = sieve(1000001);
static int mod = (int) (1e9+7);
static ArrayList<Long> primes = new ArrayList<>();
static ArrayList<Long> sumList = new ArrayList<>();
static ArrayList<Integer> divisors = new ArrayList<>();
static ArrayList<Integer> perfectSquares = new ArrayList<>();

// double a = 0.9;
// Setting the precision to 20 places
//     System.out.println(String.format("%.20f", a)); -> 0.99999999999999990000
//     double b = 1;
//     System.out.println(String.format("%.5f", b))  OR pn("%.5f",b); -> 1.00000



            // for(int i=1;i<=9;)
            // {
            //     int x=i;
            //     while(x<=n){if(x<=n)cnt++;else break;x=x*10+i;}
            //     i+=1;
            // }




            
// **********************Code Begins From Here*********************

public static void solve()
{
// ArrayList<Integer> al = new ArrayList<>();
// Map<Integer,Integer> map = new HashMap<>();
// Set<Integer> set = new TreeSet<>();
// for(Map.Entry<Integer,Integer> e:map.entrySet())pn(e.getKey()+" "+e.getValue());
// LinkedList<Integer> ll = new LinkedList<>();
// Stack<Integer>st = new Stack<>();
    int n=c.i(),x=c.i(),a[]=c.intArray(n),sum=0,ansp=n,anss=n,fg=0;
    for(int i=0;i<n;i++)
    {
        if(a[i]%x!=0)fg=1;
        sum+=a[i];
    }
    if(fg==0)pn(-1);
    else if(fg==1&&sum%x!=0)pn(n);
    else
    {
        for(int i=0;i<n;i++)
        {
            if(a[i]%x!=0)
            {
                ansp--;
                break;
            }
            ansp--;
        }
        for(int i=n-1;i>=0;i--)
        {
            if(a[i]%x!=0)
            {
                anss--;
                break;
            }
            anss--;
        }
        // pn(ansp+" "+anss);
        pn(max(ansp,anss));
    }
}
    public static void main(String[] args) throws FileNotFoundException {

//	        Scanner sc = new Scanner(System.in);
            c = new FastScanner();
            pw = new PrintWriter(System.out);
            for(long i=0;i<arr.length;i++)
            {
                if(arr[(int)i])
                {
                    primes.add(i);
                }
            }
            // for(int i=1;i<1000000;i++)
            // {
            //     sumList.add((long)(i*(i+1)/2));
            // }
            int tc = c.i(); 
            long start = System.currentTimeMillis();
            for(int t=0;t<tc;t++)
            {
                // p("Case #"+(t+1)+": ");
                solve();
            }
            long end = System.currentTimeMillis();
            if (System.getProperty("ONLINE_JUDGE") == null)
            {
                pn("The Program takes " +(end - start) + "ms");
            }
            pw.close();
        }
static int bs(int[] a,int x)
{
    int start=0,end=a.length-1;
    while(start<=end)
    {
        int mid=start+((end-start)/2);
        if(a[mid]==x)return mid;
        else if(a[mid]<x)start=mid+1;
        else end=mid-1;
    }
    return -1;
}
static String newString(String s, int k) {
            // new string
            String X = "";
     
            // Remove characters until
            // the string  is empty
            while (s.length() > 0) {
     
                char temp = s.charAt(0);
     
                // Traverse to find the smallest character in the
                // first k characters
                for (int i = 1; i < k && i < s.length(); i++) {
                    if (s.charAt(i) < temp) {
                        temp = s.charAt(i);
                    }
                }
     
                // append the smallest character
                X = X + temp;
     
                // removing the lexicographically smallest
                // character from the string
                for (int i = 0; i < k; i++) {
                    if (s.charAt(i) == temp) {
     
                        s = s.substring(0, i) + s.substring(i + 1);
                        //s.erase(s.begin() + i);
                        break;
                    }
                }
            }
     
            return X;
        }
static boolean exist(int[] a, int x) 
        {
            for (int i=0; i<a.length; i++) 
            {
                if (a[i] == x) return true;
            }
            return false;
        }
static int countPalindromicSubsequence(String str)
        {
            int N = str.length();
    
            // create a 2D array to store the count
            // of palindromic subsequence
            int[][] cps = new int[N][N];
    
            // palindromic subsequence of length 1
            for (int i = 0; i < N; i++)
                cps[i][i] = 1;
    
            // check subsequence of length L is
            // palindrome or not
            for (int L = 2; L <= N; L++) {
                for (int i = 0; i <= N-L; i++) {
                    int k = L + i - 1;
                if (str.charAt(i) == str.charAt(k)) {
                    cps[i][k] = cps[i][k - 1]
                                        + cps[i + 1][k] + 1;
                }else{
                    cps[i][k] = cps[i][k - 1]
                                        + cps[i + 1][k]
                                        - cps[i + 1][k - 1];
                }
                }
            }
            // return total palindromic subsequence
            return cps[0][N - 1];
        }
static int LCSubStr(char X[], char Y[],int m, int n)
            {
                // Create a table to store
                // lengths of longest common
                // suffixes of substrings.
                // Note that LCSuff[i][j]
                // contains length of longest
                // common suffix of
                // X[0..i-1] and Y[0..j-1].
                // The first row and first
                // column entries have no
                // logical meaning, they are
                // used only for simplicity of program
                int LCStuff[][] = new int[m + 1][n + 1];
        
                // To store length of the longest
                // common substring
                int result = 0;
        
                // Following steps build
                // LCSuff[m+1][n+1] in bottom up fashion
                for (int i = 0; i <= m; i++)
                {
                    for (int j = 0; j <= n; j++)
                    {
                        if (i == 0 || j == 0)
                            LCStuff[i][j] = 0;
                        else if (X[i - 1] == Y[j - 1])
                        {
                            LCStuff[i][j]
                                = LCStuff[i - 1][j - 1] + 1;
                            result = Integer.max(result,
                                                LCStuff[i][j]);
                        }
                        else
                            LCStuff[i][j] = 0;
                    }
                }
                return result;
            }
static List<String> subStrings(String s)
            {
                ArrayList<String> al = new ArrayList<>();
                for (int i = 0; i < s.length(); i++) {
                for (int j = i+1; j <= s.length(); j++) {
                        al.add(s.substring(i,j));
                    }
                }
                return al;
            }
static boolean isSubSequence(String str1, String str2,
            int m, int n)
            {
                // Base Cases
                if (m == 0)
                return true;
                if (n == 0)
                return false;

                // If last characters of two strings are matching
                if (str1.charAt(m - 1) == str2.charAt(n - 1))
                return isSubSequence(str1, str2, m - 1, n - 1);

                // If last characters are not matching
                return isSubSequence(str1, str2, m, n - 1);
            }
static boolean number_Is_Divisible_By_Its_Digits(long n)
        {
            long temp=n;
            while(temp>0)
            {
                long digit = temp%10;
                temp/=10;
                if(digit!=0&&n%digit!=0)return false;
            }
            return true;
        }
static int countDivisors(int n)
        {
            int cnt = 0;
            for(int i=1;i*i<=n;i++)
            {
                if(n%i==0)cnt++;
                divisors.add(i);
            }
            return cnt;
        }
static ArrayList<Integer> countDivisorsList(int n)
        {
            for(int i=1;i*i<=n;i++)
            {
                if(n%i==0)
                divisors.add(i);
            }
            return divisors;
        }
static boolean isStringSorted(String s)
        {
            for(int i=0;i<s.length()-1;i++)
            {
                if(s.charAt(i)>s.charAt(i+1))return false;
            }
            return true;
        }
static boolean isPalindromeString(String s)
        {
            String temp = "";
            for(int i=s.length()-1;i>=0;i--)
            {
                temp+=s.charAt(i)+"";
            }
            return ((s.equals(temp))?true:false);
        }
static boolean isSorted(int[] a)
        {
            int n = a.length;
            for(int i=1;i<n;i++)
            {
                if(a[i-1]>=a[i])return false;
            }
            return true;
        }
static boolean solution(int n,int x)
        {
            int sum=0;
            while(n>0)
            {
                int digit=n%10;
                n/=10;
                sum+=digit;
            }
            return (sum==x)?true:false;
        }
static ArrayList<Integer> perfectSquares(int n) 
        { 
            ArrayList<Integer> al = new  ArrayList<Integer>();
            for(int i=1;i<=n;i++)
            {
                al.add(i*i);
            }
            return al; 
        } 
static boolean checkDuplicateAll(String s)
    {
        for(int i=1;i<s.length();i++)
        {
            if(s.charAt(i)!=s.charAt(i-1))return false;
        }
        return true;
    }
static String reverseString(String s,int x)
    {
        String ans="",temp = s.substring(0,x);
        for(int i=x;i<s.length();i++)
        {
            ans = s.charAt(i)+ans;
        }
        return temp+ans;
    }
static boolean checker(int num)
    {
        String s = num+"";
        if(s.contains("0"))return false;
        int temp = num;
        while(num>0)
        {
            int digit = num%10;
            num/=10;
            if(temp%digit==0)return false;
        }
        return true;
    }
static boolean palindrome(int n)
    {
        int temp=n,rev=0;
        while(n>0)
        {
            int digit=n%10;
            n/=10;
            rev = rev*10+digit;
        }
        return (temp==rev)?true:false;
    }
static boolean checkparanthesis(String s)

    {
        Stack<Character>st = new Stack<>();
        int n = s.length();
        for(int i=0;i<n;i++)
        {
            if(s.charAt(i)=='(')st.push('(');
            else
            {
                if(st.size()==0)return false;
                else st.pop();
            }
        }
        return (st.size()==0)?true:false;
    }
static boolean[] sieve(int n)
   {
   	boolean[] isPrime = new boolean[n+1];
   	Arrays.fill(isPrime,true);
   	isPrime[0]=false;
   	isPrime[1]=false;
   	for(int i=2;i*i<=n;i++)
   	{
   		for(int j=i*i;j<=n;j+=i)
   		{
   			isPrime[j]=false;
   		}
   	}
   	return isPrime;
   }
static int[][] graph(int from[], int to[], int n)
   {
       int g[][] = new int[n][];
       int cnt[] = new int[n];
       for (int i = 0; i < from.length; i++) {
           cnt[from[i]]++;
           cnt[to[i]]++;
       }
       for (int i = 0; i < n; i++) {
           g[i] = new int[cnt[i]];
       }
       Arrays.fill(cnt, 0);
       for (int i = 0; i < from.length; i++) {
           g[from[i]][cnt[from[i]]++] = to[i];
           g[to[i]][cnt[to[i]]++] = from[i];
       }
       return g;
   }
static class Pair implements Comparable<Pair>{

       int x,y,z;
       
       Pair (int x,int y,int z){
           this.x=x;
           this.y=y;
           this.z=z;
       }
           
       public int compareTo(Pair o) {
           if (this.x == o.x)
               return Integer.compare(this.y,o.y);
           return Integer.compare(this.x,o.x);
           //return 0;
       }

       public boolean equals(Object o) {
           if (o instanceof Pair) {
               Pair p = (Pair)o;
               return p.x == x && p.y == y;
           }
           return false;
       }
       public int hashCode() {
           return new Integer(x).hashCode() * 31 + new Integer(y).hashCode();
       }
       
       @Override
       public String toString() {
           return x + " " + y;
       }
   
   } 
static String rev(String s) {
       StringBuilder sb = new StringBuilder(s);
       sb.reverse();
       return sb.toString();
   }
static long gcd(long x, long y) {
       if (y == 0) {
           return x;
       } else {
           return gcd(y, x % y);
       }
   }
static int gcd(int x, int y) {
       if (y == 0) {
           return x;
       } else {
           return gcd(y, x % y);
       }
   }
static int abs(int a, int b) {
       return (int) Math.abs(a - b);
   }
static long abs(long a, long b) {
       return (long) Math.abs(a - b);
   }
static void swap(int a,int b)
   {
       int c = b;
       b=a;
       a=c;
   }
static int max(int a, int b) {
       if (a > b) {
           return a;
       } else {
           return b;
       }
   }
static int min(int a, int b) {
       if (a > b) {
           return b;
       } else {
           return a;
       }
   }
static long max(long a, long b) {
       if (a > b) {
           return a;
       } else {
           return b;
       }
   }
static long min(long a, long b) {
       if (a > b) {
           return b;
       } else {
           return a;
       }
   }
static long pow(long n, long p, long m) {
       long result = 1;
       if (p == 0) {
           return 1;
       }
       while (p != 0) {
           if (p % 2 == 1) {
               result *= n;
           }
           if (result >= m) {
               result %= m;
           }
           p >>= 1;
           n *= n;
           if (n >= m) {
               n %= m;
           }
       }
       return result;
    }
static long pow(long n, long p) {
       long result = 1;
       if (p == 0) {
           return 1;
       }
       if (p == 1) {
           return n;
       }
       while (p != 0) {
           if (p % 2 == 1) {
               result *= n;
           }
           p >>= 1;
           n *= n;
       }
       return result;
   }
static void debug(Object... o) {
           System.out.println(Arrays.deepToString(o));
   }
static class FastScanner {
        BufferedReader br;
        StringTokenizer st;
 
        public FastScanner() throws FileNotFoundException {
            
            if (System.getProperty("ONLINE_JUDGE") == null) {
                // Input is a file
                    br = new BufferedReader(new FileReader("input.txt")); 
    
                    // PrintWriter class prints formatted representations 
                    // of objects to a text-output stream. 
                    PrintStream pw = new PrintStream(new FileOutputStream("output.txt"));
                    System.setOut(pw);
              }
            else
            {
                // Input is System.in
                br = new BufferedReader(new InputStreamReader(System.in), 32768);
                st = null;
            }
            
        }
 
        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
 
        int i() {
            return Integer.parseInt(next());
        }
 
        int[] intArray(int n) {
            int[] ret = new int[n];
            for (int i = 0; i < n; i++)
                ret[i] = i();
            return ret;
        }
 
        long l() {
            return Long.parseLong(next());
        }
 
        long[] longArray(int N) {
            long[] ret = new long[N];
            for (int i = 0; i < N; i++)
                ret[i] = l();
            return ret;
        }
 
        double d() {
            return Double.parseDouble(next());
        }
 
        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}