Grandma Capa has decided to knit a scarf and asked Grandpa Sher to make a pattern for it, a pattern is a string consisting of lowercase English letters. Grandpa Sher wrote a string s of length n.

Grandma Capa wants to knit a beautiful scarf, and in her opinion, a beautiful scarf can only be knit from a string that is a palindrome. She wants to change the pattern written by Grandpa Sher, but to avoid offending him, she will choose one lowercase English letter and erase some (at her choice, possibly none or all) occurrences of that letter in string s.

She also wants to minimize the number of erased symbols from the pattern. Please help her and find the minimum number of symbols she can erase to make string s a palindrome, or tell her that it's impossible. Notice that she can only erase symbols equal to the one letter she chose.

A string is a palindrome if it is the same from the left to the right and from the right to the left. For example, the strings 'kek', 'abacaba', 'r' and 'papicipap' are palindromes, while the strings 'abb' and 'iq' are not.

Input

The first line contains a single integer t (1 ≤ t ≤ 100) — the number of test cases. The next 2 ⋅ t lines contain the description of test cases. The description of each test case consists of two lines.

The first line of each test case contains a single integer n (1 ≤ n ≤ 10^5) — the length of the string.

The second line of each test case contains the string s consisting of n lowercase English letters.

It is guaranteed that the sum of n over all test cases does not exceed 2 ⋅ 10^5.

Output

For each test case print the minimum number of erased symbols required to make the string a palindrome, if it is possible, and -1, if it is impossible.

Example

Input


5
8
abcaacab
6
xyzxyz
4
abba
8
rprarlap
10
khyyhhyhky


Output


2
-1
0
3
2

Note

In the first test case, you can choose a letter 'a' and erase its first and last occurrences, you will get a string 'bcaacb', which is a palindrome. You can also choose a letter 'b' and erase all its occurrences, you will get a string 'acaaca', which is a palindrome as well.

In the second test case, it can be shown that it is impossible to choose a letter and erase some of its occurrences to get a palindrome.

In the third test case, you don't have to erase any symbols because the string is already a palindrome.

import java.io.*;
import java.util.Arrays;
import java.util.*;
import java.util.Scanner;
import java.util.StringTokenizer;




public class copy {


    public static boolean checker(long[] arr, long K, long diff) {
        long collect = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > diff)
                collect += arr[i] - diff;
        }

        if (collect >= K)
            return true;
        else
            return false;
    }

    public static long search(long[] arr, long K, long R) {
        long l = 0;
        long r = R;

        while (l <= r) {
            long mid = (l + r) / 2;

            if (checker(arr, K, mid)) {
                if (checker(arr, K, mid + 1))
                    l = mid + 1;
                else
                    return mid;
            } else
                r = mid - 1;
        }
        return -1;
    }

    static void sieveOfEratosthenes(int n, ArrayList<Integer> arr, ArrayList<Integer> arr1) {
        // Create a boolean array
        // "prime[0..n]" and
        // initialize all entries
        // it as true. A value in
        // prime[i] will finally be
        // false if i is Not a
        // prime, else true.
        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;
            }
        }

        // Print all prime numbers
        int x = 0;
        for (int i = 2; i <= n; i++) {
            if (prime[i] == true) {

                arr.add(i);


            }

        }
        System.out.println(arr.size());
    }

    public static boolean check(String s, int K, char ch) {
        ArrayList<Integer> arr = new ArrayList<>();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == ch)
                arr.add(i);
        }
//        if(K==1 && ch=='z')
//            System.out.println(arr);
        if (arr.size() == 0)
            return false;
        if (arr.get(0) >= K)
            return false;
        if (s.length() - 1 - arr.get(arr.size() - 1) >= K)
            return false;
        for (int i = 1; i < arr.size(); i++) {
            if (arr.get(i) - arr.get(i - 1) > K)
                return false;
        }
        return true;
    }

    public static int check(long N) {
        int sum = 0;
        while (N > 0) {
            sum += N % 10;
            N = N / 10;
        }
        return sum;

    }

    public static long call(long N) {
        long l = 1;
        long r = (long) Math.floor(Math.sqrt(N));
        while (l <= r) {
            long mid = (l + r) / 2;
            double left = N / (double) (mid) - mid;
            int right = check(mid);
            System.out.println(mid + " " + left + " " + right);
            if (mid == 10)
                System.out.println(left + " " + right);
            if (left > right)
                l = mid + 1;
            else if (right > left)
                r = mid - 1;
            else
                return mid;
        }
        return -1;
    }

    public static int path(ArrayList<ArrayList<Integer>> arr, int X, int parent, int[] gold, PriorityQueue<Integer> pq) {
        int max = 0;
        ArrayList<Integer> ch = new ArrayList<>();
        for (int i : arr.get(X)) {
            if (i != parent) {
                ch.add(path(arr, i, X, gold, pq));
            }
        }
        Collections.sort(ch, Collections.reverseOrder());
        for (int i = 1; i < ch.size(); i++)
            pq.add(ch.get(i));


        if (ch.size() == 0)
            return gold[X];
        else
            return ch.get(0) + gold[X];

    }

    public static long fac(long N, long mod) {
        if (N == 0)
            return 1;
        if(N==1)
            return 1;
        return ((N % mod) * (fac(N - 1, mod) % mod)) % mod;
    }

    public static String form(char ch, int freq) {
        String s = "";
        for (int i = 1; i <= freq; i++)
            s += ch;
        return s;
    }

    static long power(long x, long y, long p) {

        // Initialize result
        long res = 1;

        // Update x if it is more than or
        // equal to p
        x = x % p;

        while (y > 0) {

            // If y is odd, multiply x
            // with result
            if (y % 2 == 1)
                res = (res * x) % p;

            // y must be even now
            y = y >> 1; // y = y/2
            x = (x * x) % p;
        }

        return res;
    }

    // Returns n^(-1) mod p
    static long modInverse(long n, long p) {
        return power(n, p - 2, p);
    }

    // Returns nCr % p using Fermat's
    // little theorem.
    static long nCrModPFermat(long n, long r,
                              long p) {

        if (n < r)
            return 0;
        // Base case
        if (r == 0)
            return 1;

        // Fill factorial array so that we
        // can find all factorial of r, n
        // and n-r


//        System.out.println(modInverse(fac(r,p),p));
//        System.out.println(modInverse(fac(n-r,p),p));
        return ((fac(n, p) % p * (modInverse(fac(r, p), p)
                % p)) % p * (modInverse(fac(n - r, p), p)
                % p)) % p;
    }

    public static boolean check(long[] arr, long time, int M) {
        long sum = 0;
        int count = 0;
        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];
            if (sum >= time) {
                ++count;
                sum = 0;
            }
        }

        if (sum >= time)
            ++count;

        return count >= M;
    }

    public static int check(ArrayList<Integer> arr, ArrayList<Integer> arr2) {
        int l = 0, r = 0, ans = 0;
        while (l < arr.size() && r < arr2.size()) {
            if (arr.get(l) < arr2.get(r))
                ++l;
            else if (arr.get(l) > arr2.get(r))
                ++r;
            else {
                ++ans;
                ++l;
                ++r;
            }
        }
        return ans;
    }


    public static int find(int[] parent, int x) {
        if (parent[x] == x)
            return x;
        return find(parent, parent[x]);
    }

    public static void merge(int[] parent, int[] rank, int x, int y) {
        int x1 = find(parent, x);
        int y1 = find(parent, y);
        if (rank[x1] > rank[y1]) {
            parent[y1] = x1;

        } else if (rank[y1] > rank[x1]) {
            parent[x1] = y1;
        } else {
            parent[y1] = x1;
            rank[x1]++;
        }
    }

    public static int check(ArrayList<ArrayList<Integer>> arr, int e1, int e2, int N) {
        boolean[] visited = new boolean[N];
        visited[0] = true;
        int[] dist = new int[N];
        Queue<Integer> queue = new LinkedList<>();
        queue.add(0);
        Arrays.fill(dist, -1);
        dist[0] = 0;
        while (queue.size() > 0) {
            int x = queue.poll();
            for (int i : arr.get(x)) {
                if (!visited[i] || (e1 == x && e2 == i)) {
                    System.out.println(x + " " + dist[x]);
                    dist[i] = dist[x] + 1;
                    visited[i] = true;
                    queue.add(i);
                }
            }

        }


        return dist[N - 1];
    }

    static int N;

    static void rotate90Clockwise(String a[][]) {

        // Traverse each cycle
        for (int i = 0; i < N / 2; i++) {
            for (int j = i; j < N - i - 1; j++) {

                // Swap elements of each cycle
                // in clockwise direction
                String temp = a[i][j];
                a[i][j] = a[N - 1 - j][i];
                a[N - 1 - j][i] = a[N - 1 - i][N - 1 - j];
                a[N - 1 - i][N - 1 - j] = a[j][N - 1 - i];
                a[j][N - 1 - i] = temp;
            }
        }
    }


    public static void moves(String s, int i, int[] movx, int[] movy, int x, int y) {
        if (i >= s.length())
            return;
        //System.out.println(x+" hello "+y);
        if (s.charAt(i) == 'L') {
            movy[i] = y;
            movx[i] = x - 1;
            moves(s, i + 1, movx, movy, x - 1, y);
        } else if (s.charAt(i) == 'R') {
            movy[i] = y;
            movx[i] = x + 1;
            moves(s, i + 1, movx, movy, x + 1, y);
        } else if (s.charAt(i) == 'U') {
            movy[i] = y + 1;
            movx[i] = x;
            moves(s, i + 1, movx, movy, x, y + 1);
        } else {
            movy[i] = y - 1;
            movx[i] = x;
            moves(s, i + 1, movx, movy, x, y - 1);
        }

    }





    public static boolean checker(String s1, String s2, int[] arr, int mid) {
        String s = "";
        int N = s1.length();
        boolean[] visited = new boolean[N];
        for (int i = 0; i <= mid; i++)
            visited[arr[i] - 1] = true;
        for (int i = 0; i < N; i++) {
            if (!visited[i])
                s += s1.charAt(i);
        }

        int l = 0, index = -1;
        while (l < s2.length()) {
            if (s.indexOf(s2.charAt(l), index + 1) == -1)
                return false;
            else {
                index = s.indexOf(s2.charAt(l), index + 1);
                ++l;
            }
        }

        return true;
    }

    public static int check(ArrayList<Integer> possible, int X, int start) {
        int l = start, r = possible.size() - 1;

        while (l <= r) {
            int mid = (l + r) / 2;
            if (possible.get(mid) > X) {
                if (mid - 1 >= start && possible.get(mid - 1) > X)
                    r = mid - 1;
                else
                    return mid;
            } else
                l = mid + 1;
        }

        return -1;
    }


    public static int binse(div[] arr, int X, int N) {
        int l = 0, r = N - 1;

        if(arr[N-1].x<=X)
            return N;
        if(arr[0].x>X)
            return 0;
        while (l <= r) {
            int mid = (l + r) / 2;
//            if(N==2)
//            {
//                System.out.println(arr[mid].x+" hello "+X);
//            }
            if(arr[mid].x<=X)
            {
                if(mid+1<N && arr[mid+1].x<=X)
                    l=mid+1;
                else
                {
                    //System.out.println(X+" "+mid);

                    return mid+1;
                }
            }

            else
                r=mid-1;
        }
        return -1;
    }


    public static long dp(long[][] dp, int X, int[] arr, int index, long mod) {
        //System.out.println(index+" "+X);
        if (dp[index][X] != -1)
            return dp[index][X];
        int index1 = index + 1;
        int plus = (X - arr[index1] + 10) % 10;
        long ans = dp(dp, plus, arr, index - 1, mod) % mod;
        for (int i = 0; i < 10; i++) {
            if ((arr[index1] * i) % 10 == X)
                ans = (ans % mod + dp(dp, i, arr, index - 1, mod) % mod) % mod;
        }

        dp[index][X] = ans;
        return ans;


    }

    public static long gcd(long a, long b) {
        if (b == 0)
            return a;

        return gcd(b, a % b);
    }

    public static int check(int x, ArrayList<ArrayList<Integer>> arr, int parent, int dist, long[] ans, int[] child) {
        ans[0] += dist;
        int c = 0;
        for (int i : arr.get(x)) {
            if (i != parent)
                c += check(i, arr, x, dist + 1, ans, child);
        }

        child[x] = c + 1;
        return c + 1;
    }

    public static void check(int x, int parent, ArrayList<ArrayList<Integer>> arr, int[] child, long[] ans) {
        ans[x] = ans[parent] - (child[x]) + (arr.size() - child[x]);

        for (int i : arr.get(x)) {
            if (i != parent) {
                check(i, x, arr, child, ans);
            }
        }
    }

    public static void leftRotatebyOne(int arr[], int n) {
        int i, temp;
        temp = arr[0];
        for (i = 0; i < n - 1; i++)
            arr[i] = arr[i + 1];
        arr[n - 1] = temp;
    }

    public static void tick(char[][] ch, int N, int M, int x, int y, int k, int[][] copy) {

        int c = 1, size = 0;
        //System.out.println(x+" "+y);
        while (x - c >= 0 && y - c >= 0 && y + c < M && ch[x - c][y - c] == '*' && ch[x - c][y + c] == '*') {
            ++size;

            ++c;

        }
        //System.out.println(size);
        c -= 1;
        while (c >= 0) {

            copy[x - c][y - c] = Math.max(copy[x - c][y - c], size);
            copy[x - c][y + c] = Math.max(copy[x - c][y + c], size);

            --c;
        }


    }

    public static long dp(ArrayList<Integer> arr,HashMap<Integer,Long> hp)
    {
        if(arr.size()==0)
            return 0;
        long[]dp=new long[arr.size()];
        dp[0]=hp.get(arr.get(0))*arr.get(0);
        if(arr.size()==1)
            return dp[0];
        dp[1]=Math.max(arr.get(1)*(hp.get(arr.get(1))),arr.get(0)*(hp.get(arr.get(0))));
        for(int i=2;i<arr.size();i++)
        {
            int X=arr.get(i);
            dp[i]=Math.max(X*(hp.get(X))+dp[i-2],dp[i-1]);
            dp[i]=Math.max(dp[i],dp[i-2]+X*hp.get(X));
        }
//        for(int i=0;i<arr.size();i++)
//            System.out.println(dp[i]);

        return dp[arr.size()-1];
    }

    static int power(int x, int y, int p)
    {

        // Initialize result
        int res = 1;

        // Update x if it is more than or
        // equal to p
        x = x % p;

        while (y > 0) {

            // If y is odd, multiply x
            // with result
            if (y % 2 == 1)
                res = (res * x) % p;

            // y must be even now
            y = y >> 1; // y = y/2
            x = (x * x) % p;
        }

        return res;
    }

    // Returns n^(-1) mod p
    static int modInverse(int n, int p)
    {
        return power(n, p - 2, p);
    }

    // Returns nCr % p using Fermat's
    // little theorem.
    static int nCrModPFermat(int n, int r,
                             int p)
    {

        if (n<r)
            return 0;
        // Base case
        if (r == 0)
            return 1;

        // Fill factorial array so that we
        // can find all factorial of r, n
        // and n-r
        int[] fac = new int[n + 1];
        fac[0] = 1;

        for (int i = 1; i <= n; i++)
            fac[i] = fac[i - 1] * i % p;

        return (fac[n] * modInverse(fac[r], p)
                % p * modInverse(fac[n - r], p)
                % p)
                % p;
    }

    public static int check(int N,int[] dp)
    {
        if(N==0)
            return 0;
        if(dp[N]!=-1)
            return dp[N];

        if(N<10)
            return 1;
        int max=Integer.MAX_VALUE;
        int X=N;
        while(X>0)
        {
            int digit=X%10;
            if(digit!=0)
            {
                if(dp[N-digit]==-1)
                    max=Math.min(max,check(N-digit,dp));
                else
                    max=Math.min(max,dp[N-digit]);
            }
            X=X/10;

        }
        dp[N]=max+1;
        return max+1;
    }

    public static int check(int a,int b,int k,int[][] dp,int index,int N,int[] length)
    {
        if(index>=N)
            return 0;
        if(k==1)
        {
            if(N-index<a || N-index>b)
            {
                dp[index][k]=0;
                return 0;
            }
            else
            {
                dp[index][k]=1;
                length[index]=N-index;
                return 1;
            }
        }
        if(dp[index][k]!=-1)
            return dp[index][k];

        int ans=0;
        for(int i=a;i<=b;i++)
        {
            if(check(a,b,k-1,dp,index+i,N,length)==1)
            {
                length[index]=i;
                ans=1;
            }
        }
        if(ans>=1)
        {
            dp[index][k]=1;
            return 1;
        }
        else
        {
            dp[index][k]=0;
            return 0;
        }
    }

    public static long[][] ncr(int n,int r)
    {
        long[][] dp=new long[n+1][r+1];
        for(int i=0;i<=n;i++)
            dp[i][0]=1;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=r;j++)
            {
                if(j>i)
                    continue;
                dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
            }
        }

        return dp;

    }
    public static String answer(String s1,String s2)
    {
        int index=0;
        boolean status=true;
        for(int i=0;i<s2.length();i++)
        {
            if(s1.indexOf(s2.charAt(i),index)==-1)
            {
                status=false;
            }
            else
            {
                index=s1.indexOf(s2.charAt(i),index)+1;
            }
        }
        if(status)
            return "automaton";


        String arr1[]=s1.split("");
        String arr2[]=s2.split("");
        Arrays.sort(arr1);
        Arrays.sort(arr2);
        if(Arrays.equals(arr1,arr2))
            return "array";

        HashMap<Character,Integer> hp=new HashMap<>();
        for(int i=0;i<s2.length();i++)
        {
            hp.put(s2.charAt(i),0);
        }
        for(int i=0;i<s2.length();i++)
        {
            if(s1.indexOf(s2.charAt(i),hp.get(s2.charAt(i)))==-1)
            {
                return "need tree";
            }
            else
            {
                hp.put(s2.charAt(i),s1.indexOf(s2.charAt(i),hp.get(s2.charAt(i)))+1);
            }
        }

        return "both";



    }
    static boolean status=false;
    static int x1=-1,y1=-1;
    public static int dfs(ArrayList<ArrayList<Integer>> arr,int X,int[] ans,int value,int parent)
    {
        int xor=ans[X];
        for(int i:arr.get(X))
        {
            if(i!=parent)
            {
                int x=dfs(arr,i,ans,value,X);
                if(x==-1)
                    return -1;
                if(x==value)
                {
                    x1=X;
                    y1=i;
                    return -1;
                }
                xor=xor^x;
            }
        }



        return xor;
    }

    public static boolean prime(long N)
    {
        int c=0;
        for(int i=2;i*i<=N;i++)
        {
            if(N%i==0)
                ++c;
        }

        return c==0;
    }
    static int[] c;
    static boolean sta=true;
    public static int dfs(ArrayList<ArrayList<Integer>> arr,int N,int j,int[] status,boolean[] visited)
    {
        Queue<Integer> queue=new LinkedList<>();
        queue.add(j);
        status[j]=1;
        visited[j]=true;
        int[] color=new int[2];
        while(queue.size()>0)
        {
            int temp=queue.poll();
            if(temp<N)
                color[status[temp]]++;
            for(int i:arr.get(temp))
            {
                if(visited[i])
                {
                    if(status[i]==status[temp])
                        return -1;
                }
                else
                {
                    queue.add(i);
                    status[i]=1-status[temp];
                    visited[i]=true;
                }
            }
        }

        return Math.max(color[0],color[1]);
    }

    public static boolean check(String s,int N,long D,long C,long M)
    {
        int index=s.lastIndexOf('D');
        for(int i=0;i<=index;i++)
        {
            if(s.charAt(i)=='D' && D>0)
            {
                D-=1;
                C+=M;
            }
            else if(s.charAt(i)=='C' && C>0)
            {
                C-=1;
            }
            else
                return false;
        }

        return true;
    }




    public static boolean checkbounds(int x,int y,int N,int M)
    {
        return x>=0 && x<N && y>=0 && y<M;
    }

    public static void dfs(int x,int y,char[][] grid,boolean[][] visited,int N,int M)
    {
        visited[x][y]=true;
        if(checkbounds(x+1,y,N,M) && !visited[x+1][y] && grid[x+1][y]=='.')
            dfs(x+1,y,grid,visited,N,M);
        if(checkbounds(x-1,y,N,M) && !visited[x-1][y] && grid[x-1][y]=='.')
            dfs(x-1,y,grid,visited,N,M);
        if(checkbounds(x,y+1,N,M) && !visited[x][y+1] && grid[x][y+1]=='.')
            dfs(x,y+1,grid,visited,N,M);
        if(checkbounds(x,y-1,N,M) && !visited[x][y-1] && grid[x][y-1]=='.')
            dfs(x,y-1,grid,visited,N,M);
    }

    public static int bin(ArrayList<Integer> arr,int search)
    {
        int l=0,r=arr.size()-1;
        if(search<arr.get(0))
            return -1;
        if(search>arr.get(r-1))
            return r+1;
        while(l<=r)
        {
            int mid=(l+r)/2;
            if(arr.get(mid)>search)
            {
                if(mid-1>=0 && arr.get(mid-1)>search)
                    r=mid-1;
                else
                    return mid;
            }
            else
                l=mid+1;
        }

        return -1;
    }


    public static int mcbc(ArrayList<Long> arr,long search,int N,int lower)
    {
        if(search>=arr.get(N))
            return N;

        if(search<=arr.get(lower))
            return lower;
        int l=lower;
        int r=N;
        while(l<=r)
        {
            int mid=(l+r)/2;
            if(arr.get(mid)==search)
            {
                return mid;
            }

            if(arr.get(mid)>search)
            {
                if(mid-1>=lower && arr.get(mid-1)>=search)
                    r=mid-1;
                else
                {
                    if(mid-1>=lower)
                    {
                        if (Math.abs(search - arr.get(mid)) < Math.abs(search - arr.get(mid - 1)))
                            return mid;
                        else
                            return mid - 1;
                    }
                    else
                        return mid;
                }
            }

            else if(arr.get(mid)<search)
            {
                if(mid+1<=N && arr.get(mid+1)<=search)
                    l=mid+1;
                else
                {
                    if(mid+1<=N)
                    {
                        if (Math.abs(search - arr.get(mid)) < Math.abs(search - arr.get(mid + 1)))
                            return mid;
                        else
                            return mid + 1;
                    }
                    else
                        return mid;
                }
            }
        }

        return -1;

    }

    public static int check(String s,char ch)
    {
        int l=0,r=s.length()-1;
        int c=0;
        while(l<r)
        {
            if(s.charAt(l)!=s.charAt(r))
            {
                if(s.charAt(l)==ch)
                {
                    ++c;
                    ++l;
                }
                else if(s.charAt(r)==ch)
                {
                    ++c;
                    --r;
                }
                else
                {
                    return -1;
                }
            }
            else
            {
                ++l;
                --r;
            }
        }

        return c;

    }







    public static void main(String[] args) throws IOException {
        Reader.init(System.in);
        BufferedWriter output = new BufferedWriter(new OutputStreamWriter(System.out));

        int T=Reader.nextInt();
        for(int m=1;m<=T;m++) {
            int N=Reader.nextInt();
            String s=Reader.next();
            int index1=-1,index2=-1;
            int l=0,r=N-1;
            while(l<r)
            {
                if(s.charAt(l)!=s.charAt(r))
                {
                    index1=l;
                    index2=r;
                    break;
                }
                ++l;
                --r;
            }

            if(index1==-1 && index2==-1)
            {
                output.write(0+"\n");
            }
            else
            {
                int c1=check(s,s.charAt(index1));
                int c2=check(s,s.charAt(index2));
                if(c1==-1 && c2==-1)
                    output.write(-1+"\n");
                else if(c1==-1 || c2==-1)
                    output.write(Math.max(c1,c2)+"\n");
                else
                    output.write(Math.min(c1,c2)+"\n");
            }
        }



        output.flush();

    }
}



class Reader {
    static BufferedReader reader;
    static StringTokenizer tokenizer;

    static void init(InputStream input) {
        reader = new BufferedReader(
                new InputStreamReader(input));
        tokenizer = new StringTokenizer("");
    }

    static String next() throws IOException {
        while (!tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(
                    reader.readLine());
        }
        return tokenizer.nextToken();
    }

    static int nextInt() throws IOException {
        return Integer.parseInt(next());
    }

    static long nextLong() throws IOException {
        return Long.parseLong(next());
    }

    static double nextDouble() throws IOException {
        return Double.parseDouble(next());
    }
}

class div {
    int x, z;

    div(int x1,int z1) {
        x = x1;
        z=z1;

    }
}
class sortat implements Comparator<div>
{
    public int compare(div o1,div o2)
    {
        return o2.x-o1.x;
    }
}


