Description

对于给出的\(n\)个询问，每次求有多少个数对\((x,y)\)，满足\(a\le x\le b,c\le y\le d\)，且\(\gcd(x,y) = k\)，\(\gcd(x,y)\)函数为\(x\)和\(y\)的最大公约数。即计算：

\[\sum_{a\le x\le b} \sum_{c\le y\le d} [\gcd(x,y)=k]\]

Input

• 第一行一个整数\(n\)，接下来\(n\)行每行五个整数，分别表示\(a,b,c,d,k\)

Output

• 共\(n\)行，每行一个整数表示满足要求的数对\((x,y)\)的个数

Sample

Input

2
2 5 1 5 1
1 5 1 5 2

Output

14
3

HINT

• 100%的数据满足：\(1\le n\le 50000,1\le a\le b\le 50000,1\le c\le d\le 50000,1\le k\le 50000\)

Source

bzoj2301