Once in a random college it was a well known fact that the number of cows were more than the number of students in that college. If we consider the entire college as a x-y plane then there is a cow at every integer point. Once a frustrated guy wanted to have fun of looking at the girls. He found a beautiful girl at some integer point P2(x2, y2). He prayed to the god to take him to some integer point so that his view is more clear. The god responded and moved him to a random point P1(x1, y1). But poor guy, there were cows which disturbed his fun. Find the number of distinct cows between the boy and the girl including the cow (on the line joining between them) which is on the place they are standing.

Input

The first line contains T (<= 50) denoting the number of test cases.

The next T lines have four integers x1 y1 x2 y2 which describes the coordinates of the two point P1(x1, y1) and P2(x2, y2).

Absolute value of all the coordinates will be less or equal to 10000.

Output

For each test case output the required number of cows on a separate line.

Example

Input:
2
1 1 5 5
2 3 3 4

Output:
5
2