F. 345
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given $$$t$$$ test cases. Each test case is a sequence of five non-negative integers. Your goal is to reduce all five numbers to zero by applying a sequence of operations at minimum total cost.

There are two types of operations:

  • Operation $$$1$$$: Select any three consecutive elements and decrease each by $$$1$$$. Cost: $$$1$$$.
  • Operation $$$2$$$: Select any four consecutive elements and decrease each by $$$1$$$. Cost: $$$2$$$.

For each test case, determine the minimum total cost required to reduce all five integers to zero. If it is impossible, output $$$-1$$$. 

Input

The first line contains $$$t$$$ ($$$1 \leq t \leq 10^6$$$), the number of test cases. The only line of each test case includes $$$5$$$ integers, the sequence (sum of sequence $$$\le 7 * 10^9$$$).

Output

For each test case, output the minimum cost, or $$$-1$$$ if it is not possible.

Example
Input
3
1 1 2 2 1
1 1 2 1 1
1 0 0 0 0
Output
3
2
-1
Note

Problem Idea: Nyctivoe

Problem Preparation: Nyctivoe

Occurrences: Novice F