Được sinh ra nhằm phục vụ các nhu cầu thiết yếu của con người như phân lô, tách thửa mua bán, tính diện tích, toán học từ lâu đã trở thành một phần không thể thiếu của thế giới. Hình học và Số học có thể được coi là hai nhánh lớn và lâu đời nhất của Toán học, đã xuất hiện từ thời kì cổ đại.

HIện nay, khi khoa học công nghệ phát triển mạnh; Hình học cổ điển đã dần được thay thế bởi Hình học giải tích, song Số học vẫn giữ nguyên vị thế của nó, thậm chí đóng vai trò là khung xương sống cho nền công nghệ hiện đại.

Vì vậy, hôm nay bạn được cho một bài toán số học như sau:

Cho 5 số nguyên dương ~a, b, c, d, k~ ~(a \leq b, c \leq d)~.

Tính tổng các tích ~i \times j~ của các cặp ~(i, j)~ thỏa ~a \leq i \leq b~, ~c \leq j \leq d~ và ~gcd(i, j) = k~. Nói cách khác, hãy tính:

$$\displaystyle\sum_{i = a}^{b}{ \displaystyle\sum_{j = c}^{d} i \times j \times [gcd(i, j) = k]}$$

Kết quả hiện thi dưới dạng phép chia lấy dư (modulo) cho ~10^9 + 7~.

Input

• Dòng đầu chứa một số nguyên dương ~T~ ~(T≤10^5)~ là số bộ dữ liệu (testcase).

• ~T~ dòng tiếp, mỗi dòng chứa năm số nguyên ~a,b,c,d,k~ ~(1≤a≤b≤10^5,1≤c≤d≤10^5,k≤10^5)~ mô tả một bộ dữ liệu.

Output

• ~T~ dòng, mỗi dòng là đáp án cho bộ dữ liệu tương ứng.

Subtask

• Có ~20\%~ số test có ~1\le b,d\le 2000,T=1~.
• Có ~20\%~ số test có ~1\le T, b,d\le 2000, a=c=k=1~.
• Có ~20\%~ số test có ~1\le T,b,d\le 2000,k=1~.
• Có ~20\%~ số test có ~1\le T,b,d\le 2000~.
• Có ~20\%~ số test có ~1\le T,b,d\le 10^5~.

Sample Input

2
1 5 1 5 1
1 5 1 5 2

Sample Output

155
20