D :: Division

Time Limit: 10 Seconds    Memory Limit: 32768 KB

Mohammad has made a simple calculator for basic operations (i.e. Summation, Subtraction, Multiplication and Division). Most of the challenges were in implementation of Division. This is why; he decided to implement only integer-division such that the final result is also integer (floor of the real result). For example, 5/2 is equal to 2. However, implementing even this division is hard for Mohammad. He thought that “For large numbers, no one can understand how much the answer is wrong”!!!  Hence, he used a simple trick to solve this hard problem. You know that implementation of division by 2 is very simple.  So for dividing A by B (i.e. floor of A/B), he divides both of A and B by 2 until B becomes 1. Then, A is the final answer. For example, 100/20 = 50/10 = 25/5 = 12/2 = 6/1 = 6 . If A and B are in the ranges [nMin, nMax] and [mMin, mMax], respectively, would you please help Mohammad to know, how many pairs of (A,B) are there for which, his computer correctly computes the division result?

Input

The input is started by an integer 0<t≤100 followed by t testcases. Each testcase is represented by one line containing four integers nMin, nMax, mMin and mMax separated by space (0≤nMin≤nMax≤100,000 and 0<mMin≤mMax≤10,000).

Output

For each testcase, print the output in a separate line. The output is the number of pairs in the given range with a correct division-result by use of Mohammad’s calculator.

Sample Input

3
0 10 1 2
12345 67890 1234 5678
0 100000 1 10000

Sample Output

22
19204721
157192354

Submit

Source: 12th Iran Nationwide Internet Contest IV