Product Except Self

Given an array of integers \(a = [a_0, a_1, \dots, a_{n-1}]\), compute a new array \(b\) such that \(b_i = \prod_{\substack{0 \le j < n \\ j \neq i}} a_j\). In other words, for each index \(i\), the result is the product of all the elements of \(a\) except \(a_i\). You must implement the solution without using division.

Example:

Input:  [1, 2, 3, 4]
Output: [24, 12, 8, 6]

The problem should be solved for multiple test cases.

inputFormat

The first line contains an integer \(T\) denoting the number of test cases. Each test case is described over two lines. The first line of a test case contains an integer \(N\) denoting the number of elements in the array. The next line contains \(N\) space-separated integers representing the array.

Example:

2
4
1 2 3 4
3
5 6 7

outputFormat

For each test case, output a single line containing \(N\) space-separated integers where the \(i\)-th integer is equal to the product of all array elements except the \(i\)-th element.

Example:

24 12 8 6
42 35 30

## sample

2
4
1 2 3 4
3
5 6 7

24 12 8 6
42 35 30

</p>