You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小 Z 和 小 Y 今天学了下象棋。

但是棋子太多啦，小 Z 根本看不过来，所以他决定一个一个研究。

小 Z 先研究了三种棋子的移动方式：车走直，马走日，象飞田。

小 Y 想看看小 Z 学的怎么样，所以他问了小 Z 一共 $m$ 个问题，第 $i$ 个问题是 ：

• 如果棋盘大小为 $a_i\times b_i$ （格点），棋盘上只有一个 (车/马/象) 在第 $c_i$ 行第 $d_i$ 列的位置。那么经过 $e_i$ 步，这个棋子可以形成多少种不同的路径？

具体的，我们将棋子 $e_i$ 步的移动经过的 $e_i + 1$ 个点的坐标记录为一个序列。

我们认为两条路径不同，当且仅当序列中至少存在一个位置坐标不同。

可是刚学完怎么移动棋子的 小 Z 脑袋里早就一团浆糊啦，你快来帮帮他吧！

输入格式

从 chess.in 文件读入数据。

第一行一个整数，代表问题的个数 $m$ 。

接下来 $m$ 行，每行六个整数，代表每次询问为 $op_i,a_i,b_i,c_i,d_i,e_i$ 。

若 $op_i=0$ ，则询问的棋子为车；

若 $op_i = 1$ ，则询问的棋子为马；

若 $op_i = 2$ ，则询问的棋子为象；

输出格式

输出到 chess.out 文件。

共 $m$ 行，第 $i$ 行一个整数，表示第 $i$ 个问题的答案，对 $19260817$ 取膜。

样例

6
0 5 5 1 1 2
1 5 5 1 1 2
2 5 5 1 1 2
0 10 9 4 5 100
1 10 9 4 5 100
2 10 9 4 5 100 

64
12
4
8980677
14680106
12361625

数据范围

对于所有的测试数据，保证：

$1\le m\le 50\ ,\ 1\le c_i\le a_i,\ 1\le d_i\le b_i,\ 1\le a_i * b_i\le 100, \ 1 \le e_i\le 10^9$

并且对于每个测试点，$a_i\times b_i> 25$ 的数据不超过 $3$ 组。

车：如图（1）所示，车可以移动到棋盘中同一行或同一列的任意位置。

移动向量为 $[x, 0]$ 或 $[0, y]$ ，$x,y$ 为不为 $0$ 的整数（不越出棋盘边界）。

马：如图（2）所示，马可以走“日”字，移动到图示的八个位置。

移动向量为 $[2, 1],[2, -1], [1, 2], [1, -2], [-1, 2], [-1, -2], [-2, 1], [-2, -1]$ （不越出棋盘边界）。

象：如图（3）所示，象可以走“田”字，移动到图示的四个位置。

移动向量为 $[2, 2],[2, -2], [-2, 2], [-2, -2]$ （不越出棋盘边界）。