## Problem b HYSBZ - 2301

2
2 5 1 5 1
1 5 1 5 2

14
3

### Hint

$100\%$ 的数据满足：$1≤n≤50000，1≤a≤b≤50000，1≤c≤d≤50000，1≤k≤50000$

## GCD HDU - 1695

### Problem Description

Given $5$ integers: $a, b, c, d, k,$ you’re to find $x$ in $a…b$, $y$ in $c…d$ that $gcd(x, y) = k$. $gcd(x, y)$ means the greatest common divisor of $x$ and $y$. Since the number of choices may be very large, you’re only required to output the total number of different number pairs.
Please notice that, ($x=5, y=7$) and ($x=7, y=5$) are considered to be the same.

You can assume that $a = c = 1$ in all test cases.

### Input

The input consists of several test cases. The first line of the input is the number of the cases. There are no more than $3,000$ cases.
Each case contains five integers: $a, b, c, d, k, 0 < a \le b \le 100,000, 0 < c \le d \le 100,000, 0 \le k \le 100,000$, as described above.

### Output

For each test case, print the number of choices. Use the format in the example.

### Sample Input

2
1 3 1 5 1
1 11014 1 14409 9

Case 1: 9
Case 2: 736427

### Hint

For the first sample input, all the $9$ pairs of numbers are $(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 5), (3, 4), (3, 5)$.