NITT3 - Meeting and Dating

no tags 

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

 

first line T denoting the number of test cases
next T lines containing four integers x1 y1 x2 y2

 

First line contains T(<=50) denoting the number of test cases 

Next T lines has 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 each line

Example

Input:
2
1 1 5 5
2 3 3 4

Output:
5
2

hide comments
buttman: 2016-06-28 17:18:05

Don't waste your time on solving a straight line equation (y = mx + c ), precision errors would kill you.

rizkifika asanul i: 2013-01-15 14:30:37

think about minus condition

Shriram: 2012-10-03 17:30:48

@franky : if u think so...post the question id before making it tutorials

:D: 2012-10-03 06:33:05

The problem is easy in itself, has small constraints, no formatting issues I'm aware of, and requires a very basic operation to get the result. Low AC rate is because people are guessing and not solving it. It's OK of course, but doesn't make the task hard.

Francky: 2012-10-03 06:00:57

@Aditya Pande : there's yet such a problem, no need to multiply same problems.

Aditya Pande: 2012-10-03 04:14:55

why is it tutorial with only 25% submission getting AC?
the idea is very good

Last edit: 2012-10-03 04:15:33
Meraj Ahmed: 2012-10-02 18:07:01

Special cases please....i hv got the problem bt i stil am getting WA

Aditya Pande: 2012-10-02 13:29:19

AC

Last edit: 2012-10-03 10:32:11
Shrey Sengar: 2012-10-02 08:13:58

plz provide some tricky test cases!!

Aman Gupta: 2012-10-01 22:33:18

is simulation supposed to TLE?


Added by:jack(chakradarraju)
Date:2012-09-23
Time limit:0.110s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64