There are n block towers in a row, where tower i has a height of a_i. You're part of a building crew, and you want to make the buildings look as nice as possible. In a single day, you can perform the following operation:

  * Choose two indices i and j (1 ≤ i, j ≤ n; i ≠ j), and move a block from tower i to tower j. This essentially decreases a_i by 1 and increases a_j by 1. 



You think the ugliness of the buildings is the height difference between the tallest and shortest buildings. Formally, the ugliness is defined as max(a)-min(a). 

What's the minimum possible ugliness you can achieve, after any number of days?

Input

The first line contains one integer t (1 ≤ t ≤ 1000) — the number of test cases. Then t cases follow.

The first line of each test case contains one integer n (2 ≤ n ≤ 100) — the number of buildings.

The second line of each test case contains n space separated integers a_1, a_2, …, a_n (1 ≤ a_i ≤ 10^7) — the heights of the buildings.

Output

For each test case, output a single integer — the minimum possible ugliness of the buildings.

Example

Input


3
3
10 10 10
4
3 2 1 2
5
1 2 3 1 5


Output


0
0
1

Note

In the first test case, the ugliness is already 0.

In the second test case, you should do one operation, with i = 1 and j = 3. The new heights will now be [2, 2, 2, 2], with an ugliness of 0.

In the third test case, you may do three operations: 

  1. with i = 3 and j = 1. The new array will now be [2, 2, 2, 1, 5], 
  2. with i = 5 and j = 4. The new array will now be [2, 2, 2, 2, 4], 
  3. with i = 5 and j = 3. The new array will now be [2, 2, 3, 2, 3]. 

The resulting ugliness is 1. It can be proven that this is the minimum possible ugliness for this test.
import java.util.*;
import java.io.*;


public class c6{

    static class Pair{
        int first;
        int last;
        public Pair(int first , int last){
            this.first = first;
            this.last = last;
        }
    
        public int getFirst(){
            return first;
        }
        public int getLast(){
            return last;
        }
    }

    static final int M = 1000000007;

    // Fast input 
    static class Hrittik_FastReader{
        StringTokenizer st;
        BufferedReader br;
        public int n;
        public Hrittik_FastReader(){
            br=new BufferedReader(new InputStreamReader(System.in));
        }
        String next(){
            while(st==null || !st.hasMoreTokens()){
                try {
                    st=new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        String nextLine(){
            String str="";
            try {
                str=br.readLine().trim();
            } catch (Exception e) {
                e.printStackTrace();
            }
            return str;
        }
        double nextDouble(){
            return Double.parseDouble(next());
        }
        int nextInt(){
            return Integer.parseInt(next());
        }
        long nextLong(){
            return Long.parseLong(next());
        }
        
        
    }
    // Fast output
    static class Hrittik_FastWriter {
        private final BufferedWriter bw;

        public Hrittik_FastWriter() {
            this.bw = new BufferedWriter(new OutputStreamWriter(System.out));
        }

        public void println(Object object) throws IOException {
            print(object);
            bw.append("\n");
        }

        public void print(Object object) throws IOException {
            bw.append("" + object);

        }

        public void close() throws IOException {
            bw.close();
        }
    }

    // GCD of two integers
    private static int gcd(int a , int b){
        if(b == 0) return a;
        return gcd(b, a%b);
    }

    // GCD of two long integers
    private static long gcd(long a , long b){
        if(b == 0) return a;
        return gcd(b, a%b);
    }

    // LCM of two integers
    private static int lcm(int a, int b) {
        return a / gcd(a, b) * b;
    }

    // LCM of two long integers
    private static long lcm(long a, long b) {
        return a / gcd(a, b) * b;
    }

    // swap two elements of an array
    private static void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    // calculating x ^ y
    private static long power(long x, long y){
        long res = 1; 
        x = x % M;
        while(y > 0){
            if ((y & 1) == 1){
                res = (res * x) % M;
            }
            y = y >> 1; 
            x = (x * x) % M;
        }
        return res;
    }

    static void sortPairByFirst(Pair arr[]){
        Arrays.sort(arr , new Comparator<Pair>(){
            @Override public int compare(Pair p1 , Pair p2){
                return p1.first - p2.first;
            }
        });
    }

    static void sortPairByLast(Pair arr[]){
        Arrays.sort(arr , new Comparator<Pair>(){
            @Override public int compare(Pair p1 , Pair p2){
                return p1.last - p2.last;
            }
        });
    }
    static long binpow(long a, long b) {
        if (b == 0)
            return 1;
        long res = binpow(a, b / 2);
        if (b % 2 == 0)
            return res * res * a;
        else
            return res * res;
    }
    static long function(long n){
        long k = -1;
        while(n != 0){
            n/=2;
            k++;
        }
        return k;
    }


    public static void main(String[] args) {

        try {
            Hrittik_FastReader Sc =new Hrittik_FastReader();
            Hrittik_FastWriter out = new Hrittik_FastWriter();
            int t = Sc.nextInt();
            outer : while(t-- > 0){
                // write your code here
                long a = Sc.nextLong();
                long b = Sc.nextLong();
                long k = ((b - a + 1) % 2) == 1 ? ((b - a + 1) / 2 + 1) : ((b - a + 1) / 2);
                long ans1 = b;
                ans1 = ans1 - power(2, function(b));
                ans1 += 1;
                long ans2 = power(2 , function(b));
                ans2 = ans2 - power(2 , function(b) - 1);
                long max = Math.max(ans1*1 , ans2 * 1);
                max = Math.max(max , k * 1);
                long sol = (b-a+1)-max;
                out.println(sol);
                
        
        
        
        
        
        
        
        
                
                
            }
            out.close();
        }

        catch (Exception e) {
            return;
        }
    }
}




