Product Except Self

You are given an array of n integers. Your task is to compute a new array result where the i^th element is the product of all the numbers in the original array except the one at index i. In other words, for an input array \( a = [a_0, a_1, \dots, a_{n-1}] \), you should construct an array \( result \) such that:

[ result[i] = \prod_{\substack{0 \leq j < n \ j \neq i}} a_j ]

Note: You are not allowed to use division in your solution. Instead, you should compute the result in \( O(n) \) time using prefix and suffix products.

Examples:

• For [1, 2, 3] the output should be [6, 3, 2], since \(6 = 2 \times 3\), \(3 = 1 \times 3\), and \(2 = 1 \times 2\).
• For [2, 3, 4, 5] the output should be [60, 40, 30, 24].

inputFormat

The first line of input contains an integer \( T \) representing the number of test cases. Each test case is described in two parts:

• The first integer is \( n \), the number of elements in the array.
• It is followed by \( n \) space-separated integers representing the array.

All input is read from standard input (stdin).

outputFormat

For each test case, output a single line containing \( n \) space-separated integers, which represent the product of the array except self for each position. The output is sent to standard output (stdout).

## sample

3
3 1 2 3
4 2 3 4 5
3 1 0 -2

6 3 2
60 40 30 24
0 -2 0

</p>