Problem 2244. -- Teleportation

2244: Teleportation

Time Limit: 1 Sec  Memory Limit: 128 MB   64bit IO Format: %lld
Submitted: 38  Accepted: 24
[Submit][Status][Web Board]


        Hovey just learnt a powerful skill from the failurc of his chasing MMs: teleportation. He can teleport from point (x , y) to another point (x', y') by using one of the two following methods.
        T1: ( x' , y' ) <--  ( x-y , 2y-x )
        T2: ( x' , y' ) <--  ( 2y-x , 2x-3y )
        You should notice that all the numbers are non-negative integers and calculated modulo 1000.
        Now you are going to find out the minimum times of teleportation to get from point A to point B.                                                .


        There are multiple test cases. The first line contains an integer T, the number of cases.
        In each cases, there are four non-negative integers in a single line, (Xa,Ya), (Xb, Yb), indicating  the query point A and B. All integers are less than 1000.


        For each test case, output one line contairung the minimum times ofteleportation to get from A to B. If there is no solution, output -1 instead.

Sample Input

37 859 13 416

Sample Output




[Submit][Status][Web Board]