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.
/**
 *    Author : pradumn
**/
#include<bits/stdc++.h>
using namespace std;
#define Fast_io ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define ll long long
#define M 1000000007
#define M2 998244353
#define rep(i,a,b) for(i=a;i<b;i++)
#define pb push_back
#define mp make_pair
#define umap unordered_map
#define pqueue priority_queue
#define all(v) v.begin(),v.end()
#define ft first
#define sc second
#define nl "\n"
#define mxe  *max_element
#define mne  *min_element
#define sz(x) (int)(x.size())
#define rev(x) reverse(all(x))
#define itr(it, a) for(auto it = a.begin(); it != a.end(); it++)
#define srt(x) sort(all(x))
#define bs(x,v) binary_search(all(x),v)
#define lb(x,v) lower_bound(all(x),v)
#define ub(x,v) upper_bound(all(x),v)
#define prt(x) cout<<x<<nl;
#define inf INT_MAX
#define ninf INT_MIN
typedef unsigned long long ull;
typedef long double lld;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pi;
typedef vector<vi> vvi;
typedef map<int,int> mi;
typedef vector<pi> vpi;
typedef set<int> si;


#ifndef ONLINE_JUDGE
#define deb(c) cerr << #c <<" : "; _print(c); cerr << endl;
#else
#define deb(c)
#endif
void _print(ll t) {cerr << t;}
void _print(int t) {cerr << t;}
void _print(string t) {cerr << t;}
void _print(char t) {cerr << t;}
void _print(lld t) {cerr << t;}
void _print(double t) {cerr << t;}
void _print(ull t) {cerr << t;}
template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(set <T> v);
template <class T, class V> void _print(map <T, V> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.ft); cerr << ","; _print(p.sc); cerr << "}";}
template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
void init_code()
{
  Fast_io;
  #ifndef ONLINE_JUDGE
    // freopen("Input.txt","r",stdin);
    // freopen("Output.txt","w",stdout);
    freopen("error.txt","w",stderr);
  #endif
}

// ll fac[100000001];ll fact(int n){fac[0]=1;fac[1]=1;for (int i = 2; i <=n; i++){fac[i]=i*fac[i-1];}return fac[n];}
// ll c(int n,int r){ fact(n);return fac[n]/(fac[r]*fac[n-r]);}
// void func();void kcst(){int t;cin>>t;for(int i=1;i<=t;i++){cout<<"Case #"<<i<<": ";func();}}
// bool isprime(int n){if(n==2){return 1;}else if(n%2==0){return 0;}else{for(int i=3;i*i<=n;i+=2){if(n%i==0){return 0;}}return 1;}}
// ll modularExponentiation(ll x,ll n,int m){if(n==0)return 1;else if(n%2 == 0) return modularExponentiation((x*x)%m,n/2,m);
// else return (x*modularExponentiation((x*x)%m,(n-1)/2,m))%m;}


/**************************Code starts from here**********************************/




// int dp[200001];
 
void func()
{
 int n;
 cin>>n;
 vi a(n);
 vi b(n);
 for(int i=0;i<n;i++)
 {
  cin>>a[i];
 }
 b=a;
 rev(b);
 for(int i=0;i<n/2;i++)
{
b[i]=(-1*b[i]);
 
}
 if(n%2==1)
 {
  int l=lcm(a[0],a[n/2]);

  b[n/2]=(b[n/2]>0?l/abs(a[n/2]):-1*(l/abs(a[n/2])));
  if(b[0]*a[0]<0)
  b[0]=(b[0]>0?b[0]+l/abs(a[0]):b[0]-(l/abs(a[0])));
  else
   b[n-1]=(b[n-1]>0?b[n-1]+l/abs(a[0]):b[n-1]-(l/abs(a[0])));
}

for(int i=0;i<n;i++)
{
  cout<<b[i]<<" ";
}
cout<<nl;
}


int main()
{
init_code();
double start1 = (double)clock();
int t=1;
cin>>t;
while(t--)
func();
double stop1 =(double)clock();
double duration = (stop1-start1)/CLOCKS_PER_SEC;
#ifndef ONLINE_JUDGE
cerr << "Time: " << duration << endl;
#endif
}