CHOCDIST - Chocolate distribution

In Dystopia, chocolates are being distributed to children waiting in a queue. The distribution proceeds as follows. Each chocolate bar is rectangular in shape with integer edge lengths. If the chocolate bar is a square, it is given away completely to the first child in the queue. Otherwise the largest possible square piece of chocolate is broken off from the chocolate bar and given to the first child. After a child receives his share of chocolate, he leaves the queue. The remaining portion of the chocolate bar is dealt with in the same fashion and the whole or a portion of it is given to the next child in the queue.

For example, if we start with a 5x3 chocolate bar, the first child in the queue receives a 3x3 chocolate bar, leaving a 2x3 bar. The second child gets a 2x2 bar while the third and fourth children get 1x1 bars. Thus four children have been fed using the 5x3 bar.

The Dystopian government has got a carton of chocolate bars to be distributed to children in the country. To make sure that maximum inequality is achieved while distributing chocolates, the chocolate bars in the carton are all of different sizes. For every i such that M<=i<=N and every j such that P<=j<=Q (where M,N,P,Q are integers) there is exactly one chocolate bar of length i and breadth j in the carton. Here a bar of length i and breadth j is considered to be different from a bar of length j and breadth i.

Given the values of M,N,P,Q find the number of children that can be fed with the chocolate in the carton.

Input

The first line of the input contains the number of test cases, T (<=1000)

Following this are T lines, each describing a test case with four integers M,N,P,Q separated by spaces (1<=M<=N<=100000000, 1<=P<=Q<=1000)

Output

Output T lines, each containing an integer : The number of children that can be fed using the chocolate in the carton

Example

Input:
2
1 2 1 2
3 4 4 5

Output:
6
14

Added by:Raziman T V
Date:2011-02-13
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:IOPC2011

hide comments
2012-03-24 19:16:24 Xx100m
@ admin: can u please tell me why my code (submission id: 6718057) is getting TLE. Is there any other optimization possible that i haven't used yet.
2011-07-12 15:59:42 Kunal
What should be the complexity of optimal solution?? O(q*q) ??
2011-05-28 10:55:39 Troy
Modular arithmetic...
2011-05-16 12:56:10 foreigner
i am using DP , but still not working for high values of m and n, please gprovide some hints....
2011-04-11 19:13:15 S
how is the op of 2nd test case 14?isn't it 11?
2011-04-25 12:57:52 pawan gambhir
what is runtime error (SIGSEGV) ...
2011-02-14 06:32:16 Raziman T V
I have increased the time limit to 3s. Looked at your solution - the timeout is not because of the inefficiency of JAVA but the suboptimality of your algorithm
2011-02-14 05:28:18 Alex Anderson
Seems like it might be near impossible with Java

Last edit: 2011-02-14 05:52:24
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.