AVCHESS - Chess Board of Avengers

no tags 

The Avengers become divided, both over how to approach Loki and the revelation that S.H.I.E.L.D. plans to harness the Tesseract to develop weapons as a deterrent against hostile extraterrestrials. The argument is raised between Captain America, Iron man and Thor each having his own point to keep. Agent Natasha Romanoff comes up with a non-violent solution to this argument by suggesting a variant of the game of chess for three players. This time chessboard contains only a knight, a rook and a bishop. In this game, first Captain America takes his turn, next Iron Man and then Thor. After Thor's turn, this sequence repeats.

  • Captain America can only move knight, Iron Man rook, and Thor bishop and each player can move their respective piece to an empty position.
  • The rook can move any number of squares horizontally or vertically, but may not leap over other pieces.
  • The bishop can move any number of squares diagonally, but may not leap over other pieces.
  • The knight' move forms an "L"-shape: two squares vertically and one square horizontally, or two squares horizontally and one square vertically. The knight is the only piece that can leap over other pieces.


The objective of game is to place rook at the initial position of knight, bishop at initial position of rook and knight at initial position of bishop. That is, if the initial position of knight, rook and bishop is (x1, y1), (x2, y2) and (x3, y3), respectively, then the final position of them should be (x3, y3), (x1, y1), (x2, y2) respectively.

Input

The first line of the input contains an integer T denoting the number of test cases.
Each test case consists of exactly one line containing 6 space separated integers x1 y1 x2 y2 x3 y3.
x1 y1 represents the initial position of Knight.
x2 y2 represents the initial position of Rook.
x3 y3 represents the initial position of Bishop.

  • T=5
  • 0x1, y17
  • 0x2, y27
  • 0x3, y37
  • No pair of initial positions are equal, i.e., (x1, y1) != (x2, y2) && (x1, y1) != (x3, y3) && (x2, y2) != (x3, y3)

Output

For each test case, print the minimum number of turns required to achieve this objective.

If the desired configuration is not reachable print -1.

 

Example

Input:
1
0 0 5 1 3 3 

Output: 
5

Explanation

Starting Points of Knight[0,0], Rook[5,1] and Bishop[3,3] can be changed to Knight[3,3], Rook[0,0], Bishop[5,1] in the following five steps:
Knight - [0,0] to [1,2]
Rook - [5,1] to [5,0]
Bishop - [3,3] to [5,1]
Knight - [1,2] to [3,3]
Rook - [5,0] to [0,0]

There is no way to get the required final configuration in less than 5 steps.


hide comments
David: 2021-12-01 16:50:40

Great problem - lots of subtle defects fixed along the way to AC. Thanks to @simes for the assistance. First Java solution.

Last edit: 2021-12-03 18:09:25
Swarna: 2013-12-14 08:27:57

nice problem ^_^

Jacob Plachta: 2013-11-17 19:32:17

It seems that, in each turn, the current piece *must* be moved to a new location.


Added by:BLANKRK
Date:2013-11-15
Time limit:1s-5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Code Weavers 2013