You are given an N x 5 matrix where each row represents a mathematical relationship between five variables: a, b, c, d, and e.

For every row, the variables strictly satisfy the following equation: e = (a + b + c) * d

In each row, exactly one of the five variables is unknown. The unknown variable is represented by the value -1. Your task is to calculate and output the exact integer value of the missing variable for each row.

Input Format

• The first line contains a single integer N, representing the number of rows in the matrix.
• The next N lines each contain five space-separated integers representing the values of a, b, c, d, and e respectively for that row.

Output Format

• For each row, print a single integer on a new line representing the calculated value of the missing variable (the one initially marked as -1).

Constraints

• 1 <= N <= 10^5
• It is guaranteed that there will be exactly one -1 in every row.
• It is guaranteed that a valid integer solution exists for the missing variable.
• All given non-negative variables and the resulting missing variable will fit within a standard 64-bit signed integer (long long).

Sample Input 1

3
-1 2 3 4 40
1 1 1 2 -1
2 0 0 -1 10

Sample Output 1

5
6
5

Explanation

• Test Case 1: The given values are b=2, c=3, d=4, e=40, and a is missing. Substituting into the formula: 40 = (a + 2 + 3) * 4 => 40 = (a + 5) * 4 => 10 = a + 5 => a = 5.
• Test Case 2: The given values are a=1, b=1, c=1, d=2, and e is missing. Substituting into the formula: e = (1 + 1 + 1) * 2 => e = 3 * 2 => e = 6.
• Test Case 3: The given values are a=2, b=0, c=0, e=10, and d is missing. Substituting into the formula: 10 = (2 + 0 + 0) * d => 10 = 2 * d => d = 5.