GCD

Time Limit: 5 Seconds    Memory Limit: 44032 KB

Shamir has recently learnt about Greatest Common Divisor between numbers. He counted there are 7 pairs of numbers between 1 and 6 (inclusive) that their GCD(Greatest Common Divisor) equals 2: {(2,2),(2,4),(2,6),(4,2),(4,6),(6,2),(6,4)}. He wants to count all pairs of numbers (X,Y) such that x1 ≤ X ≤ x2 , y1 ≤ Y ≤ y2 and gcd(X,Y) = d.

The greatest common divisor (gcd) of two or more integers (when at least one of them is not zero), is the largest positive integer that divides the numbers without a remainder. For example, the GCD of 8 and 12 is 4.

 

Input

The input contains several test-cases. First line of input contains an integer T indicating number of test-cases and is followed by T lines each containing 5 integers x1, x2 , y1, y2 and d describing the test-case.

1 ≤ x1, x2 , y1, y2 ,d ≤1000000, x1 ≤ x2 , y1 ≤ y2

Output

For each test case print total number of pairs explained above on a single line.

 

Sample Input

3
1 6 1 6 2
1 9 3 11 3
1 10 1 10 1

Sample Output

7
7
63

Submit

Source: 12th Iran Nationwide Internet Contest III