Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Four Points

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou are given four different integer points $$$p_1$$$, $$$p_2$$$, $$$p_3$$$ and $$$p_4$$$ on $$$\mathit{XY}$$$ grid.

In one step you can choose one of the points $$$p_i$$$ and move it in one of four directions by one. In other words, if you have chosen point $$$p_i = (x, y)$$$ you can move it to $$$(x, y + 1)$$$, $$$(x, y - 1)$$$, $$$(x + 1, y)$$$ or $$$(x - 1, y)$$$.

Your goal to move points in such a way that they will form a square with sides parallel to $$$\mathit{OX}$$$ and $$$\mathit{OY}$$$ axes (a square with side $$$0$$$ is allowed).

What is the minimum number of steps you need to make such a square?

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

Each test case consists of four lines. Each line contains two integers $$$x$$$ and $$$y$$$ ($$$0 \le x, y \le 10^9$$$) — coordinates of one of the points $$$p_i = (x, y)$$$.

All points are different in one test case.

Output

For each test case, print the single integer — the minimum number of steps to make a square.

Example

Input

3 0 2 4 2 2 0 2 4 1 0 2 0 4 0 6 0 1 6 2 2 2 5 4 1

Output

8 7 5

Note

In the first test case, one of the optimal solutions is shown below:

In the second test case, one of the optimal solutions is shown below:

In the third test case, one of the optimal solutions is shown below:

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/07/2021 23:05:26 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|