C. Large Summation
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array a consisting of n element a1, a2, ..., an. For each element ai you must find another element aj (i ≠ j), such that the summation of ai and aj mod (109 + 7) (i.e. (ai + aj) % (109 + 7)) is as maximal as possible.

Can you help judges by solving this hard problem?

Input

The first line contains an integer T, where T is the number of test cases.

The first line of each test contains an integer n (2 ≤ n ≤ 105), where n is the size of the array a.

The second line of each test case contains n integers a1, a2, ..., an (0 ≤ ai < 109 + 7), giving the array a.

Output

For each test case, print a single line containing n space separated elements, such that the ith element is the answer to the ith element in the array a (i.e. the maximum value of (ai + aj) % (109 + 7)).

Example
Input
2
3
1 2 3
2
1000000000 1000000000
Output
4 5 5
999999993 999999993
Note

As input/output can reach huge size it is recommended to use fast input/output methods: for example, prefer to use scanf/printf instead of cin/cout in C++, prefer to use BufferedReader/PrintWriter instead of Scanner/System.out in Java.