Migrated from Lutece 2868 丁香树

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

若纳水輨，如转丸珠。夫岂可道，假体如愚。荒荒坤轴，悠悠天枢。
载要其端，载同其符。超超神明，返返冥无。来往千载，是之谓乎。

——《二十四诗品 · 二十四 · 流动》

高三楼旁边的一棵丁香树很奇怪，按理说丁香花都是一簇一簇的，而这棵丁香树的花与树枝竟形成了树形结构，可以看做一棵有根无标号的树。更奇怪的是，这棵丁香树的花都没有颜色！最奇怪的是，这棵丁香树可以随意改变自己的形态，就好像流动了起来。

Kanade 决定给这棵丁香树的花涂色，这棵丁香树上共有 $n$ 朵花，一朵丁香花有 $4$ 个花瓣（当然有更多花瓣的丁香花，但是这棵紫丁香的花瓣均有 $4$ 瓣）。Kanade 会随机地选择这 $n$ 朵花的一些花瓣涂色。

Kanade 规定了每一朵花的权值，把一朵花看做树的一个节点，那么这朵花的权值为这个节点的子节点权值和与每个子节点带来的加成的和，如果这朵花没有子节点，则权值为 $0$。一朵花的子节点带来的加成是子节点每个花瓣带来的加成的和。如果子节点的一个花瓣与其父节点的相同位置的花瓣涂色状态相同（都涂色或都不涂色），带来一个加成，若不同则带来另一个加成。

Kanade 会等概率地涂色，树也会等概率地改变自己的形态。涂后 Kanade 想知道，根节点权值的期望是多少。

Input

第一行一个正整数 $T\ (1\le T\le 10^4)$，表示数据组数。

对于每组数据，第一行一个正整数 $n\ (2\le n\le 10^9)$，意义如题目描述。

接下来 $4$ 行，每行两个非负整数 $a,b\ (0\le b\lt a\lt 998244353)$，第 $i$ 行描述 $i$ 位置的花瓣带来的权值加成，如果一朵花与其子节点的花的第 $i$ 位置的花瓣涂色状态相同，则带来 $a$ 的权值加成，否则带来 $b$ 的权值加成。

Output

对于每组数据输出一行一个整数，表示根节点权值的期望。期望可能是个分数，但它一定是个有理数，即可以写成 $\frac{a}{b}$ 的形式，其中 $a\in \mathbb{N},b\in \mathbb{N}_+$，且 $(a,b)=1$。请输出 $a \times b^{-1}$ 对 $998244353$ 取模后的值，其中 $b^{-1}$ 表示 $b$ 在模 $998244353$ 意义下的逆元。

Samples

1
3
3 2
6 1
1 0
2 1

16

Resources

The 20th UESTC Programming Contest Preliminary