蒜斜一直怀疑自己和北大算协是高维空间中某个分形的两个分支。支撑这个观点的证据有很多。其一，他们都叫蒜斜（算协）；其二，他们都低调、奢华、有内涵，帅气、阳光、有魅力；其三，他们的好朋友都叫镁团（美团）。

蒜斜也常常思考，在高维空间里，他和北大算协之间有什么关系呢？这个问题过于高端，让我们先来看一个二维的版本吧。

定义如下的分形：

1. $0$ 级的 o 是一个 $1\times 1$ 的字符矩阵，里面包含了一个字符 o。
2. $0$ 级的 x 是一个 $1 \times 1$ 的字符矩阵，里面包含了一个字符 x。
3. $i$ 级的 x 和 o 均是 $3^i \times 3^i$ 的字符矩阵，它们通过将 $i-1$ 级别的 x,o 通过如下方式排列得到（左侧表示 x，右侧表示 o）：

xox ooo
oxo oxo
xox ooo

举例来说，二级的 x 和 o 分别为：

xoxoooxox ooooooooo
oxooxooxo oxooxooxo
xoxoooxox ooooooooo
oooxoxooo oooxoxooo
oxooxooxo oxooxooxo
oooxoxooo oooxoxooo
xoxoooxox ooooooooo
oxooxooxo oxooxooxo
xoxoooxox ooooooooo

一个人穷极一生，接触到的也只不过是世界的一部分。在这个二维的版本中，这个范围可以表示成 $n$ 级别的 x 中的一个子矩形：它包含第 $xl$ 行至第 $xr$ 行的第 $yl$ 列至 $yr$ 列。

人一生中接触到的一些事物是连续的，就像这个分形中的 o 一样；而又有一些事物是突然发生的，就像这个分形中的 x 一样。而这些突然发生的事物又把连续的一生给划分成了一块一块丰富多彩的篇章。在这题中，蒜斜希望你计算 $n$ 级 x 的某一个子矩形中，o 被分割成了多少个四连通块。

给定一个矩阵，两个字符 o 在同一个四连通块里，当且仅当从一个 o 出发，不停的向上下左右移动，可以在只经过 o 的情况下到达另一个 o。

输入格式

输入第一行是一个整数 $t(1 \leq t \leq 50)$，表示数据组数。

对于每组数据，输入包含一行五个整数 $n, xl, xr, yl, yr (1 \leq n \leq 35, 1 \leq xl \leq xr \leq 3^n, 1 \leq yl \leq yr \leq 3^n)$。

输出格式

对于每组数据，输出一行一个整数表示 o 的四连通块个数。答案可能很大，你只需要输出对 $998244353$ 取模后的值。

样例一

input

5
1 1 3 1 3
2 1 9 1 9
2 3 5 4 8
2 1 6 2 7
35 1 50031545098999707 1 50031545098999707

output

4
12
3
5
679477107

explanation

这儿以第三组数据为例，在第三组数据中，涉及到的子矩形为：

oooxo
xoxoo
oxoox

显然，在这个子矩形中，o 被 x 划分成了 $3$ 个四连通块。

限制与约定

Small Task: $n \leq 35, xr - xl \leq 2$。

Large Task: $n \leq 35$。

时间限制：$2\texttt{s}$

空间限制：$512\texttt{MB}$

下载

样例数据下载