Product Except Self

Given an integer array ( \textbf{nums} ) of length ( n ), your task is to compute an output array ( \textbf{result} ) such that ( \textbf{result}[i] ) is equal to the product of all the elements of ( \textbf{nums} ) except ( \textbf{nums}[i] ).

For example, if ( \textbf{nums} = [1, 2, 3, 4, 5] ), then ( \textbf{result} = [120, 60, 40, 30, 24] ).

You are not allowed to use division. Your algorithm should ideally run in ( O(n) ) time and use constant extra space (excluding the output array).

inputFormat

The input is given via standard input (stdin).

The first line contains an integer ( T ) representing the number of test cases. Each test case consists of two lines:
- The first line contains an integer ( n ), the number of elements in the array.
- The second line contains ( n ) space-separated integers representing the elements of the array.

outputFormat

For each test case, output a single line on standard output (stdout) containing ( n ) space-separated integers. The ( i^{th} ) integer should be the product of all elements of the array except the element at index ( i ).## sample

2
5
1 2 3 4 5
3
3 2 1

120 60 40 30 24
2 3 6