题目描述

雷马古特亲王在我们之前的故事中成功地遇到了乌尤夫,之后,乌尤公主向雷马古特人介绍了一种名为尼克斯尼亚克的新型国际象棋。唯一允许的棋手是一种特殊的骑士。

棋盘为$(N+1)*(M+1)$。每个行和列编号为以下图:

这里 $N + 1 = 5 + 1$是行数,$M + 1 = 4 + 1$是列数。我们还给出了两个整数$P和Q,$并被告知在游戏开始时,(x,y) - (行号,列数)的块 - 其中$x <= P$和$y <= Q$已经被$Knight$占用。

在游戏期间,我们可以选择单个骑士移动,而Knight在(x,y)的唯一允许的动作是$(x + a,y + b)或(x + c,y + d)$。但在运动期间,它的位置必须在棋盘上,而不是被另一个骑士占据。我们的目的是将那个象棋手移动到最后端$(N,M)$。(上面的描述意味着一旦你选择了棋手,你只能在以下步骤中移动那个棋手)

同时,我们假设$3 <= N,M <= 100000,0 <= P < N,0 <= Q < M,1<=a,b,c,d。Uyuw$公主想知道本质上不同的游戏的数量。两个游戏被称为“不同”,只有当我们在开始时选择不同的棋手或在某个时间执行不同的运动时。

警告:即使$a = c,b = d$,我们也调用$(+a,+b)$和$(+c,+d)$不同运动!

输入

您应该阅读第一行的测试用例Z的数量$- Z <= 100$。

以下每行表示单个测试用例,由 8 个整数$N、M、P、Q、a、b、c 和 d$ 组成。上述这些整数的含义。

输出

每个测试用例输出一条线,显示游戏的全部可能性。我们保证这个数字小于10^500。 输入数 1

2
3 3 0 0 1 1 1 1
5 4 2 1 1 1 2 1

输出数位 1

8
7

来源

POJ 月刊, 朱泽苑