在图论中，最大生成树是一个子图，它是一棵树，并且连接了所有顶点，使得权值之和最大。最大生成森林是图中每个连通分量的最大生成树的并集。

给定一个大型无向图 $G = (V, E)$，其中 $V = \{(x, y) : 1 \le x, y \le 2,000,000,000; x, y \in \mathbb{Z}\}$，初始时 $E = \emptyset$。你的任务是编写一个程序来支持操作 $x_1, y_1, x_2, y_2, c$：

• 首先，在 $G$ 中添加一些边。如果 $x_1 \le a_1, a_2 \le x_2$，$y_1 \le b_1, b_2 \le y_2$ 且 $|a_1 - a_2| + |b_1 - b_2| = 1$，则在 $(a_1, b_1)$ 和 $(a_2, b_2)$ 之间添加一条权值为 $c$ 的边。
• 其次，计算添加边后 $G$ 的最大生成森林的权值。

输入格式

输入的第一行包含一个整数 $T$，表示测试用例的总数。 每个测试用例的第一行包含一个整数 $n$，表示操作的数量。接下来的 $n$ 行描述了这些操作。每行包含 5 个整数 $x_1, y_1, x_2, y_2, c$，由空格分隔。

数据范围

• $1 \le T \le 500$
• $1 \le n \le 100$
• $1 \le x_1 \le x_2 \le 2,000,000,000$
• $1 \le y_1 \le y_2 \le 2,000,000,000$
• $1 \le c \le 1,000,000,000$
• 至多有 20 个测试用例满足 $n > 50$。

输出格式

对于每次操作，输出一行，表示当前最大生成森林的权值对 $10^9 + 7$ 取模的结果。

样例

样例输入 1

2
3
2 2 3 3 1
1 2 2 3 2
1 1 1 3 5
1
1 1 2000000000 2000000000 1000000000

样例输出 1

3
8
16
999998642