Robert and Sienna are running, with Florence police catching up fast. They make a swift left, and found a shallow alley, with a strange looking metal gate at the end. Their only way out: open the gate.

The gate has a horizontal bar, with N sections on it. Each section has an input portal, and a number written below that portal. They have to enter correct number at each portal to open the gate.

The hint given below the portals:

Take out three, take out four,
Below the voids, take no more.
Tire your brain, let the blood flow,
Plunge it deepest, let it go.

Robert figured: For each section, keep subtracting 3 or 4 from the number written in that section, until the number becomes negative. Try to get the smallest number possible using these operations. Then enter the number in that portal.

They entered the numbers and quickly got in. Can you guess what they answered?

Input

First line contains T, number of test cases. Then each test case contains two lines.

First line of each test case contains N, the number of sections on the horizontal bar.

Second line contains N space separated numbers, containing the numbers on the N sections.

Output

For each testcase, output one line of N space separated number, containing the numbers that must be entered in the portals to get the gate open.

Sample

Input
2
3
0 2 1
4
3 2 1 -1

Output
-4 -2 -3
-4 -2 -3 -1

Constraints

1 <= T<= 1000

1 <= N<= 100000

Sum of all N's in a test file will not exceed 10⁵.

Each number in each section is between -10⁹ to +10⁹ inclusive.