KNMOVE - Knight Move

no tags 

Daniel is a chess player. At his free time, he usually plays chess with his family or his friends. But, sometimes they have their own activities, so Daniel can't play chess. He spends his time to learn about knight's move. He has 1,000 x 1,000 chessboard, numbered from 1 to 1,000. He wants to move his knight from (a,b) to (1,1) with minimum movement. Help Daniel to solve it.

Input

The input file consists of several lines.

The first line contains a single number t representing the number of question Daniel asked. [ 1<=t<=1,000 ]

The next t lines contains a and b representing knight's position on the chessboard. [ 1<= a,b <= 1,000 ]

Output

The output file should contains t lines.

The i-th line should contain one number – the minimum number of knight's movement.

Example

Input:
2
3 5
7 4

Output: 2
3
 

hide comments
syamphanindra: 2017-05-22 19:04:10

one go... got ac :) must precompute all and then perform test cases

ov3rk1ll: 2016-06-22 16:40:08

@macbox do some precomputation

macbox: 2016-06-20 14:06:29

Getting TLE with bfs what technique should i use to optimize code ?


Added by:AVM
Date:2016-06-13
Time limit:0.050s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:Own Problem