对于正整数 $a$ 和 $b$，如果存在正整数 $k$ 使得 $a = b k$，则称 $b$ 整除 $a$ 或者 $a$ 被 $b$ 整除，也称 $a$ 是 $b$ 的倍数，记作 $b \mid a$。
对于正整数 $a$ 和 $b$，如果存在正整数 $m$ 使得 $a \mid m$ 且 $b \mid m$，则称 $m$ 是 $a$ 和 $b$ 的公倍数，而 $a$ 和 $b$ 的所有公倍数中最小的正整数称为最小公倍数，记作 $\mathrm{lcm}(a, b)$。
给定正整数 $a, b, c, d$ 和 $P$，我们对于正整数 $n$ 和 $m$ 定义 $f(n, m)$ 为满足 $n^a \mid \mathrm{lcm}(m^b, k)$ 且 $m^c \mid \mathrm{lcm}(n^d, k)$ 的最小正整数 $k$，请你计算
$$\left(\sum_{i = 1}^{P}\sum_{j = 1}^{P}{f(i, j)}\right) \bmod (10^9 + 7)$$
的值，其中 $(10^9 + 7)$ 是一个质数。
第一行包含一个正整数 $T$，表示有 $T$ 组测试数据。
接下来依次给出每组测试数据。对于每组测试数据：
仅一行，包含五个整数 $a, b, c, d$ 和 $P$，含义见题目描述。
保证在一行中的每个整数之间有恰好一个空格，没有其他额外的空格。
保证所有的数据满足 $1 \leq T \leq 200,$ $1 \leq a, b, c, d \leq 10^9,$ $1 \leq P \leq 1000$。
保证 $90\%$ 的数据满足 $1 \leq P \leq 100$。
对于每组数据，输出一行，包含一个整数，表示题目所求式子的值。
2
1 1 1 1 1
1 1 1 1 21
6对于第二组数据，因为 $f(1, 1) = f(2, 2) = 1,$ $f(1, 2) = f(2, 1) = 2$，所以输出 $6$。