Vupsen and Pupsen were gifted an integer array. Since Vupsen doesn't like the number 0, he threw away all numbers equal to 0 from the array. As a result, he got an array a of length n.

Pupsen, on the contrary, likes the number 0 and he got upset when he saw the array without zeroes. To cheer Pupsen up, Vupsen decided to come up with another array b of length n such that ∑_{i=1}^{n}a_i ⋅ b_i=0. Since Vupsen doesn't like number 0, the array b must not contain numbers equal to 0. Also, the numbers in that array must not be huge, so the sum of their absolute values cannot exceed 10^9. Please help Vupsen to find any such array b!

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 (2 ≤ n ≤ 10^5) — the length of the array.

The second line contains n integers a_1, a_2, …, a_n (-10^4 ≤ a_i ≤ 10^4, a_i ≠ 0) — the elements of the array a.

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

Output

For each test case print n integers b_1, b_2, …, b_n — elements of the array b (|b_1|+|b_2|+… +|b_n| ≤ 10^9, b_i ≠ 0, ∑_{i=1}^{n}a_i ⋅ b_i=0).

It can be shown that the answer always exists.

Example

Input


3
2
5 5
5
5 -2 10 -9 4
7
1 2 3 4 5 6 7


Output


1 -1
-1 5 1 -1 -1
-10 2 2 -3 5 -1 -1

Note

In the first test case, 5 ⋅ 1 + 5 ⋅ (-1)=5-5=0. You could also print 3 -3, for example, since 5 ⋅ 3 + 5 ⋅ (-3)=15-15=0

In the second test case, 5 ⋅ (-1) + (-2) ⋅ 5 + 10 ⋅ 1 + (-9) ⋅ (-1) + 4 ⋅ (-1)=-5-10+10+9-4=0.
    import java.io.BufferedReader;
    import java.io.FileInputStream;
    import java.io.FileNotFoundException;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.util.*;
import java.util.concurrent.LinkedBlockingDeque;
import java.io.PrintStream;
    import java.io.PrintWriter;
    import java.io.DataInputStream;

        public class Solution {

            public static boolean Local(){
                try{ 
                    return System.getenv("LOCAL_SYS")!=null;
                }catch(Exception e){
                    return false;
                }
            }   

            public static boolean LOCAL;

            static class FastScanner {

                    BufferedReader br;
                    StringTokenizer st ;

                    FastScanner(){
                        br =  new BufferedReader(new InputStreamReader(System.in));
                        st = new StringTokenizer("");
                    }

                    FastScanner(String file) {

                        try{
                            br =  new BufferedReader(new InputStreamReader(new FileInputStream(file)));
                            st = new StringTokenizer("");
                        }catch(FileNotFoundException e) {
                            // TODO Auto-generated catch block
                            System.out.println("file not found");
                            e.printStackTrace();
                        }
                        
                    }
                    

                    String next() {
                        while (!st.hasMoreTokens())
                            try {
                                st = new StringTokenizer(br.readLine());
                            } catch (IOException e) {
                            }
                        return st.nextToken();
                    }

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

                    long nextLong() {
                        return Long.parseLong(next());
                    }
                    String readLine() throws IOException{
                        return br.readLine();
                    }
                }
                                    
            static class Pair<T,X> {

                T first;
                X second;
                
                Pair(T first,X second){
                    this.first = first;
                    this.second = second;
                }

                @Override
                public int hashCode(){
                    return Objects.hash(first,second);
                }

                @Override
                public boolean equals(Object obj){
                    return obj.hashCode() == this.hashCode();
                }

            }

        
        static PrintStream debug = null;
        
        
        static long mod = (long)(Math.pow(10,9) + 7); 
        

        public static void main(String[] args) throws Exception {
            
            FastScanner s = new FastScanner();

            LOCAL = Local();

            //PrintWriter pw = new PrintWriter(System.out);


            
            if(LOCAL){
                s = new FastScanner("src/input.txt");
                PrintStream o = new PrintStream("src/sampleout.txt");
                debug = new PrintStream("src/debug.txt");
                System.setOut(o);
            //  pw = new PrintWriter(o);
            }


            
            long mod = 1000000007;

        
            int tcr =  s.nextInt();                  
            
            StringBuilder sb = new StringBuilder();


            for(int tc=0;tc<tcr;tc++){
                
                int n = s.nextInt();
                
                int arr[] = new int[n];
                
                for(int i=0;i<n;i++){
                    arr[i] = s.nextInt();
                }

               // println(n+"--");

                long prefix[] = new long[n+1];
                for(int i=1;i<=n;i++){
                    prefix[i] = prefix[i-1] + (arr[i-1]*1l);
                }

                int max_k = (int)Math.sqrt(2*n);

                long dp[][] = new long[n+1][max_k+1];

                Arrays.fill(dp[n],Long.MAX_VALUE);
                for(int i=0;i<=n;i++){
                    dp[i][0] =Long.MAX_VALUE;
                }

                for(int i=n-1;i>=0;i--){
                    if(i == n-1){
                        dp[i][1] = arr[i];
                        continue;
                    }
                    for(int j=1;j<=max_k;j++){
                        long op1 = dp[i+1][j];
                        long op2 = 0l;
                        if(i+j<n && ((prefix[i+j] - prefix[i]) < dp[i+j][j-1])){
                            op2 = (prefix[i+j] - prefix[i]);
                        }
                        dp[i][j] = Math.max(op1,op2);
                    }
                }
                dbg(debug,dp);
                int ans = 0;
                for(int i=1;i<=max_k;i++){
                    if(dp[0][i] > 0){ans++;}
                }
                sb.append(ans+"\n");

            }

            print(sb.toString());
        }


        public static List<int[]> print_prime_factors(int n){
        
            List<int[]> list = new ArrayList<>();
            
            for(int i=2;i<=(int)(Math.sqrt(n));i++){
    
                if(n % i == 0){
                    
                    int cnt = 0;
                    
                    while( (n % i) == 0){
                        n = n/i;
                        cnt++;
                    }
    
                    list.add(new int[]{i,cnt});
                }
            }
    
            if(n!=1){
                list.add(new int[]{n,1});
            }

            return list;
        }

        public static boolean inRange(int r1,int r2,int val){
            return ((val >= r1) && (val <= r2));
        }

        static int len(long num){
            return Long.toString(num).length();
        }

        static long mulmod(long a, long b,long mod)
        {
            long ans = 0l;
            
            while(b > 0){
                long curr = (b & 1l);
                if(curr == 1l){
                    ans = ((ans % mod) + a) % mod;
                }
                
                a = (a + a) % mod;

                b = b >> 1;
            }

            return ans;
        }


        public static void dbg(PrintStream ps,Object... o) throws Exception{
            if(ps == null){
                return;
            }
            Debug.dbg(ps,o);
        }

        public static long modpow(long num,long pow,long mod){

            long val = num;
            long ans = 1l;

            while(pow > 0l){
                
                long bit = pow & 1l;

                if(bit == 1){
                    ans = (ans * (val%mod))%mod;
                }

                val = (val * val) % mod;
                pow = pow >> 1;
            }

            return ans;

        }

        public static char get(int n){
            return (char)('a' + n);
        }

        public static long[] sort(long arr[]){
            List<Long> list = new ArrayList<>();
            for(long n : arr){list.add(n);}
            Collections.sort(list);
            for(int i=0;i<arr.length;i++){
                arr[i] = list.get(i);
            }
            return arr;
        }

        public static int[] sort(int arr[]){
            List<Integer> list = new ArrayList<>();
            for(int n : arr){list.add(n);}
            Collections.sort(list);
            for(int i=0;i<arr.length;i++){
                arr[i] = list.get(i);
            }
            return arr;
        }

        // return the (index + 1)
        // where index is the pos of just smaller element
        // i.e count of elemets strictly less than num
        public static int justSmaller(long arr[],long num){
            //  System.out.println(num+"@");
            int st = 0;
            int e = arr.length - 1;

            int ans = -1;

            while(st <= e){

                int mid = (st + e)/2;

                if(arr[mid] >= num){
                    e = mid - 1;
                }else{
                    ans = mid;
                    st = mid + 1;
                }

            }


            return ans + 1;

        }
        public static int justSmaller(int arr[],int num){
            //  System.out.println(num+"@");
            int st = 0;
            int e = arr.length - 1;

            int ans = -1;

            while(st <= e){

                int mid = (st + e)/2;

                if(arr[mid] >= num){
                    e = mid - 1;
                }else{
                    ans = mid;
                    st = mid + 1;
                }

            }


            return ans + 1;

        }
        
        //return (index of just greater element)
        //count of elements smaller than or equal to num

        public static int justGreater(long arr[],long num){
            int st = 0;
            int e = arr.length - 1;

            int ans = arr.length;

            while(st <= e){
                
                int mid = (st + e)/2;

                if(arr[mid] <= num){
                    st = mid + 1;
                }else{
                    ans = mid;
                    e = mid - 1;
                }
            }

            return ans;

        }

        public static int justGreater(int arr[],int num){
            int st = 0;
            int e = arr.length - 1;

            int ans = arr.length;

            while(st <= e){
                
                int mid = (st + e)/2;

                if(arr[mid] <= num){
                    st = mid + 1;
                }else{
                    ans = mid;
                    e = mid - 1;
                }
            }

            return ans;

        }

        

        public static void println(Object obj){
            System.out.println(obj.toString());
        }

        public static void print(Object obj){
            System.out.print(obj.toString());
        }

        public static int gcd(int a,int b){
            if(b == 0){return a;}
            return gcd(b,a%b);
        }

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

            return gcd(b,a%b);
        }

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



        public static List<Integer> sieve(){
        
                List<Integer> prime = new ArrayList<>();

                int arr[] = new int[100001];

            Arrays.fill(arr,1);

            arr[1] = 0;
            arr[2] = 1;

            for(int i=2;i<=100000;i++){
                
                if(arr[i] == 1){
                    
                    prime.add(i);

                    for(long j = (i*1l*i);j<100001;j+=i){
                        arr[(int)j] = 0;
                    }
                }
            }

            return prime;
        }

        static boolean isPower(long n,long a){
            
            long log = (long)(Math.log(n)/Math.log(a));

            long power = (long)Math.pow(a,log);

            if(power == n){return true;}

            return false;
        }


        private static int mergeAndCount(int[] arr, int l,int m, int r)
        {

            // Left subarray
            int[] left =  Arrays.copyOfRange(arr, l, m + 1);

            // Right subarray
            int[] right = Arrays.copyOfRange(arr, m + 1, r + 1);

            int i = 0, j = 0, k = l, swaps = 0;

            while (i < left.length && j < right.length) {
                if (left[i] <= right[j])
                    arr[k++] = left[i++];
                else {
                    arr[k++] = right[j++];
                    swaps += (m + 1) - (l + i);
                }
            }
            while (i < left.length)
                arr[k++] = left[i++];
            while (j < right.length)
                arr[k++] = right[j++];
            return swaps;
        }

        // Merge sort function
        private static int mergeSortAndCount(int[] arr, int l,int r)
        {

            // Keeps track of the inversion count at a
            // particular node of the recursion tree
            int count = 0;

            if (l < r) {
                int m = (l + r) / 2;

                // Total inversion count = left subarray count
                // + right subarray count + merge count

                // Left subarray count
                count += mergeSortAndCount(arr, l, m);

                // Right subarray count
                count += mergeSortAndCount(arr, m + 1, r);

                // Merge count
                count += mergeAndCount(arr, l, m, r);
            }

            return count;
        }

        static class Debug{
            //change to System.getProperty("ONLINE_JUDGE")==null; for CodeForces
            public static final boolean LOCAL = System.getProperty("ONLINE_JUDGE")==null;

            

            private static <T> String ts(T t) {
                if(t==null) {
                    return "null";
                }
                try {
                    return ts((Iterable) t);
                }catch(ClassCastException e) {
                    if(t instanceof int[]) {
                        String s = Arrays.toString((int[]) t);
                        return "{"+s.substring(1, s.length()-1)+"}\n";
                    }else if(t instanceof long[]) {
                        String s = Arrays.toString((long[]) t);
                        return "{"+s.substring(1, s.length()-1)+"}\n";
                    }else if(t instanceof char[]) {
                        String s = Arrays.toString((char[]) t);
                        return "{"+s.substring(1, s.length()-1)+"}\n";
                    }else if(t instanceof double[]) {
                        String s = Arrays.toString((double[]) t);
                        return "{"+s.substring(1, s.length()-1)+"}\n";
                    }else if(t instanceof boolean[]) {
                        String s = Arrays.toString((boolean[]) t);
                        return "{"+s.substring(1, s.length()-1)+"}\n";
                    }
                    try {
                        return ts((Object[]) t);
                    }catch(ClassCastException e1) {
                        return t.toString();
                    }
                }
            }
            private static <T> String ts(T[] arr) {
                StringBuilder ret = new StringBuilder();
                ret.append("{");
                boolean first = true;
                for(T t: arr) {
                    if(!first) {
                        ret.append(", ");
                    }
                    first = false;
                    ret.append(ts(t));
                }
                ret.append("}");
                return ret.toString();
            }
            private static <T> String ts(Iterable<T> iter) {
                StringBuilder ret = new StringBuilder();
                ret.append("{");
                boolean first = true;
                for(T t: iter) {
                    if(!first) {
                        ret.append(", ");
                    }
                    first = false;
                    ret.append(ts(t));
                }
                ret.append("}\n");
                return ret.toString();
            }
            public static void dbg(PrintStream ps,Object... o) throws Exception {
                if(LOCAL) {
                    System.setErr(ps);
                    System.err.print("Line #"+Thread.currentThread().getStackTrace()[2].getLineNumber()+": [\n");
                    for(int i = 0; i<o.length; i++) {
                        if(i!=0) {
                            System.err.print(", ");
                        }
                        System.err.print(ts(o[i]));
                    }
                    System.err.println("]");
                }
            }
        }

    }