SP62 IMP - The Imp

An Imp jumps on an infinite chessboard. Moves possible for the Imp are described by two pairs of integers: (a,b) and (c,d) - from square (x,y) the Imp can move to one of the squares: (x+a,y+b), (x-a,y-b), (x+c,y+d), (x-c,y-d). We want to know for which square different from (0,0) to which the Imp can jump from (0,0) (possibly in many moves) the value |x|+|y| is the lowest. ### Task Write a program which - reads from standard input two pairs (a,b) and (c,d) of integers, different from (0,0), describing moves of the Imp, - determines a pair of integers (x,y) different from (0,0), for which the Imp can jump (possibly in many moves) from square (0,0) to square (x,y) and for which the value |x|+|y| is the lowest. - writes out to standard output the value |x|+|y|.

Ten test cases. Each test consists of four numbers a,b,c,d in one line, separated by spaces. -100000

For every test case your program should write a single line with a number equal the lowest possible value |x|+|y|.