题目描述

小林喜欢画画。他有1张width * heigh的纸，他在纸上操作步骤如下：从直线X = xfold对折（是把左边的纸折到右边上面）;把纸竖直对折成cnt+l等份,就是把最上面的折到下面，共操作cnt次。现在小林画一个实心矩形，左下角的坐标是（xl ,yl）,右上角也标是（x2，y2）。注意（x1 ,y1）和（X2,y2>是把纸折完之后的坐标，（0,0>是左下角坐标，小林画的那些格子的墨水都会渗到它对应的下层的那些格子。最后再次展开纸。 例如，如图所示，小林有一张5 x 6的纸,他把直线x=2 左边的纸折到右边去，cnt=2，则把纸竖直对折成3份。然后画一个矩形（白色），左下角坐标是（1,1）右上角坐标是（3,2）。再次展开得到最后一张图。

现给出纸的width、height、xfold、cnt、x1、y1、x2、y2,请问画完之后，还有多少个格子没被渗到颜色

输入格式

第一行K，表示有K组测试数据，$1 \leq K \leq 5$。

每组测试数据一行，共8个整数：width、height、xfold、cnt、x1、y1、x2、y2。其中$1 \leq$ width ，height $\leq 10^9，0 \leq $xfold $\leq$ width,$0 \leq$cnt$\leq1000$,cnt+1能被height整除，$0 \leq x1 < x2 \leq$max(xfold,width-xfold),$0 \leq y1 < y2 \leq$height / (cnt + 1)。

输出格式

输出K行，每一行一个整数，表示画完之后还有多少个格子没被渗到颜色。

样例数据

input

1
5 6 2 2 1 1 3 2

output

21

数据规模与约定

时间限制：$1 \text {s}$

空间限制：$64 \text {MB}$