ADV04F1 - Four Chips (Hard)

There is a n × 1 board. Its cells are numbered with integers from 1 to n. First four cells have indistinguishable chips in them. In one turn you can move one chip to the neighbouring cell or move it symmetrically relatively any other chip (i.e. if you move a chip in cell 10 symmetrically relative to the chip in cell 13 it will end up in cell 16), given that the chip won't leave the board and each cell will have no more than one chip. You need to determine the minimum number of turns needed to reach a certain configuration of chips.

Input

The first line of input contains number T - the amount of test cases. Next T lines consist of four integers a1, a2, a3 and a4 — the numbers of cells where the chips should be in the final configuration.

Constraints

1 <= T <= 10000
1 <= a1 < a2 < a3 < a4 <= n
n = 70

Output

For each test case print single integer - the answer to the problem in the statement.

Example

Input:
2
1 2 3 4
1 3 4 6

Output:
0
1


Added by:Spooky
Date:2010-11-14
Time limit:3.289s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2024-07-16 10:47:41
The time limit is very tight. Consider maintaining a global queue (if using bfs) and global visited array (of 4th degree). Use the fact that n is constant and starting position is constant.
2021-12-26 07:51:11
TL is too tight...
input:
5
1 6 7 8
26 45 46 69
4 6 7 8
1 2 3 69
1 6 54 70
output:
4
10
4
12
9
2021-09-10 17:55:54
More cases, please?
2021-06-05 05:03:39
can anyone explain me this question ?
2011-02-10 17:05:03 LeppyR64
Is it allowed for two chips to occupy the same cell at any time during the processing?

Edit: I answered my own question, no, it's not allowed.

Edit: Its Clearly mentioned in the problem. "Given that the chip won't leave the board and each cell will have no more than one chip. "

Last edit: 2011-02-13 12:26:43
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.