Product Except Self

Given an array of integers, your task is to construct a new array where the element at each index is the product of all the numbers in the input array except the one at that index. Specifically, for an array \(nums\) of size \(n\), the result at index \(i\) is given by:

$$ result[i] = \prod_{\substack{j=0 \\ j \neq i}}^{n-1} nums[j] $$

Please note that the input may contain zeros and even a single element (in which case, output 1). The solution should be efficient and run in \(O(n)\) time while using \(O(n)\) extra space.

inputFormat

The input is given via standard input (stdin). The first line contains a single integer \(T\) which represents the number of test cases. Each test case is described as follows:

• The first line of each test case contains an integer \(n\), the number of elements in the array.
• The second line contains \(n\) space-separated integers denoting the elements of the array.

outputFormat

For each test case, output a single line on standard output (stdout) containing \(n\) space-separated integers where the \(i\)th integer is the product of all elements of the input array except the element at index \(i\).

## sample

2
4
1 2 3 4
3
2 3 4

24 12 8 6
12 8 6

</p>