Description

小林喜欢画画。他有一张width * height的纸，他在纸上的操作步骤如下：从直线 x=xfold 对折（是把左边的纸折到右边上面）；把纸竖直对折成 cnt+1 等份，就是把最上面的折到下面，共操作 cnt 次。现在小林画一个实心矩形，左下角的坐标是（x1,y1），右上角坐标是（x2,y2）。注意（x1,y1）和（x2,y2）是把纸折弯之后的坐标，（0,0）是左下角坐标，小林画的那些格子的墨水都会渗到它对应的下层的那些格子。最后再次展开纸。

例如，小林有一张 5*6 的纸，他把直线 x=2 左边的纸折到右边去，cnt=2，则把纸竖直对折成3份。然后画一个矩形（白色），左下角坐标是（1,1），右上角坐标是（3,2）。再次展开得到最后一张图。

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

Input Format

第一行K，表示有 K 组测试数据。

每组测试数据一行，共8个整数，width、height、xfold、cnt、x1、y1、x2、y2。

Output Format

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

1
5 6 2 2 1 1 3 2

21

Hint

数据范围：

1 <= K <= 15。

1 <= width，height <= 10^9，0 <= xfold <= width，0 <= cnt <= 1000，cnt+1能被height整除，0 <= x1 < x2 <= max( xfold,width-xfold )，0 <= y1 < y2 <= height/( cnt+1 )。