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 63Submit
Source: 12th Iran Nationwide Internet Contest III