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.
//BISMILAHIRAHMANIR RAHIM
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define int               long long int
#define endl        "\n"
#define pb                push_back
#define ppb               pop_back
#define pf                push_front
#define ppf               pop_front
#define all(x)            (x).begin(),(x).end()
#define allr(x)       (x).rbegin(),(x).rend()
#define uniq(v)           (v).erase(unique(all(v)),(v).end())
#define sz(x)             (int)((x).size())
#define fr                first
#define sc                second
#define pii               pair<int,int>
#define loop(i,a,b)        for(int i=a;i<b;i++)
#define mem1(a)           memset(a,-1,sizeof(a))
#define mem0(a)           memset(a,0,sizeof(a))
#define ppc               __builtin_popcount
#define ppcll             __builtin_popcountll
#define br                break
#define con               continue


// typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
template<typename T1,typename T2>istream& operator>>(istream& in,pair<T1,T2> &a){in>>a.fr>>a.sc;return in;}
template<typename T1,typename T2>ostream& operator<<(ostream& out,pair<T1,T2> a){out<<a.fr<<" "<<a.sc;return out;}
template<typename T,typename T1>T amax(T &a,T1 b){if(b>a)a=b;return a;}
template<typename T,typename T1>T amin(T &a,T1 b){if(b<a)a=b;return a;}
template <typename T> using ordered_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
const long long INF=1e18;
const int32_t M=1e9+7;
const int32_t MM=998244353;
 
// priority_queue<pii, vector<pii>, greater<pii> >q;
const int mx = 2e5+5;
int phi[1000000];
int mark[1000000];
vector<int>prime;
const int N = 10000;
int lp[10005];
vector<int> pr;
int bigmod(int base,int power,int mod){
 int res =1;
 while(power>0){
     if(power%2) res = ((res%mod) * (base%mod))%mod;
 
     base = ((base%mod)*(base%mod))%mod;
     power/=2;
 }
 return res;
}

void euler_phi(){
 for(int i=1;i<=mx;i++)phi[i]=i;
 for(int i=2;i<=mx;i++){
     if(phi[i]==i){
         phi[i]=i-1;
         for(int j=i;j<=mx;j+=i)phi[j]=(phi[j]/i)*(i-1);
     }
 }
}


void linear_seive(){
 
 for (int i=2; i<=N; ++i) {
     if (lp[i] == 0) {
         lp[i] = i;
         pr.push_back (i);
     }
     for (int j=0; j<(int)pr.size() && pr[j]<=lp[i] && i*pr[j]<=N; ++j)
         lp[i * pr[j]] = pr[j];
 }
}


void seive(){
 for(int i=2;i<=mx;i++){
     if(mark[i]==0){
         prime.pb(i);
         for(int j=i+i;j<=mx;j+=i)mark[j]=1;
     }
 }
}



signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);

    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output1.txt","w",stdout);
    #endif

    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;

        int a[n+1];
        for(int i=1;i<=n;i++)cin>>a[i];

        if(n%2){
            if(a[1]+a[2]!=0){
                cout<<-a[3]<<" "<<-a[3]<<" "<<a[1]+a[2]<<" ";
            }else if(a[1]+a[3]!=0){
                cout<<-a[2]<<" "<<a[1]+a[3]<<" "<<-a[2]<<" ";
            }else cout<<a[2]+a[3]<<" "<<-a[1]<<" "<<-a[1]<<" ";

            for(int i=4;i+1<=n;i++)cout<<-a[i+1]<<" "<<a[i]<<" ";
            cout<<endl;
        }
        else{
            for(int i=1;i+1<=n;i++)cout<<-a[i+1]<<" "<<a[i]<<" ";
            cout<<endl;
        }

    }

    


    
    
}
///ALHAMDULILLAH//