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