Radio Base

In 20XX, many years of research have paid off, and wireless energy transmission and reception technology has been put into practical use. By using this technology, it has become possible to supply power to depopulated areas where it was not possible to draw power lines because the cost was not worth it. This technology has some quirks and can send energy as far as it can go, but it has the limitation that it can only receive radio waves at specific locations. In other words, if the world is represented by a two-dimensional plane, the positive direction of the y-axis is north, and the positive direction of the x-axis is east, radio waves can be received only at points where both the x-coordinate and y-coordinate are integers (phase). It's a problem). In addition, radio waves can only be transmitted in eight directions (east, west, south, north, northeast, northwest, southeast, and southwest) when viewed from the base (equipment capable of transmitting and receiving radio waves).

Due to this restriction, it may not be possible to directly supply radio waves to the target location, but this can be solved by setting up a relay station. For example, energy cannot be sent directly from coordinates (0, 0) to (3, 7), but this can be solved by placing a relay station at (3, 3).

You are an engineer at an electric power company, and a customer asks you to set up a base in a certain place. However, in order to avoid the problem that the power stops just because a certain part breaks down, when laying a new base, it is necessary to receive energy from two or more bases that have already been built. Also, only one base can be built at a time, and two bases cannot be placed in the same location. Given two existing base locations, ask for at least how many more bases need to be built to meet customer demand.

Input

The input consists of multiple datasets.

The first line of input is given the number of datasets N (0 <N ≤ 300). Each dataset is given in the following N lines.

One dataset consists of one line of strings, given six integers separated by spaces as shown below.

x1 y1 x2 y2 X Y

(x1, y1) and (x2, y2) are the coordinates of the two existing bases, and (X, Y) are the coordinates of the destination. The x, y coordinate values ​​given by the input satisfy -100000000 ≤ x, y ≤ 100000000. The coordinates of the two existing bases are guaranteed to be different.

Output

For each dataset, output the number of bases that need to be laid in one line.

Example

Input

4 0 1 3 2 0 1 1 1 2 2 9 9 0 0 1 4 5 5 0 0 1 4 5 10

Output

0 1 2 3

inputFormat

Input

The input consists of multiple datasets.

The first line of input is given the number of datasets N (0 <N ≤ 300). Each dataset is given in the following N lines.

One dataset consists of one line of strings, given six integers separated by spaces as shown below.

x1 y1 x2 y2 X Y

(x1, y1) and (x2, y2) are the coordinates of the two existing bases, and (X, Y) are the coordinates of the destination. The x, y coordinate values ​​given by the input satisfy -100000000 ≤ x, y ≤ 100000000. The coordinates of the two existing bases are guaranteed to be different.

outputFormat

Output

For each dataset, output the number of bases that need to be laid in one line.

Example

Input

4 0 1 3 2 0 1 1 1 2 2 9 9 0 0 1 4 5 5 0 0 1 4 5 10

Output

0 1 2 3

样例

4
0 1 3 2 0 1
1 1 2 2 9 9
0 0 1 4 5 5
0 0 1 4 5 10

0
1
2
3

</p>