Background

A sea of skeletons in the Necropolis!

The anti-magic ball of the Stronghold!

The three back-row shooters of the Tower!

The armor-piercing Behemoth of the Fortress!

The full magic-resistance Black Dragon of the Dungeon!

Tower ↑

---

Team Shen is here to play Heroes of Might and Magic 3.

Problem Description

Necromancy is the core spell of the Necropolis faction.

A hero with Necromancy can gain a certain number of skeletons after each battle, based on the number of enemies killed. We use integers $A,B$ to describe Necromancy. Let $F_{A,B}(i)$ denote the number of skeletons obtained by killing $i$ enemies. Then:

$$F_{A,B}(1)=A,F_{A,B}(2)=B,F_{A,B}(x)=\lfloor \sqrt{F_{A,B}(x-2)F_{A,B}(x-1)}\rfloor+1\;(x \ge 3)$$

Now Team Shen wants to recruit a hero in the tavern. Hero 1 has Necromancy parameters $A,B$, and Hero 2 has Necromancy parameters $X,Y$. To compare whose Necromancy is stronger, compute the value of the following expression:

$$\prod_{i=1}^nF_{X,Y}(i)-F_{A,B}(i)$$

Of course Team Shen knows how to do it, but he wants to test you.

Input Format

The first line contains an integer $T$, the number of queries.

The next $T$ lines each contain five integers $n,A,B,X,Y$.

Output Format

Output $T$ lines. For each query, output the answer modulo $998244353$.

It is recommended to use sqrtl and long double for square roots.

4
5 2 10 1 8
11 4 5 1 4
19 1 9 8 10
114 51 4 1919 810

998244317
998242817
939523984
604148977

Hint

Sample Explanation

In the sample explanation, let $F_{A,B}$ be $f$, and $F_{X,Y}$ be $g$.

For the first query:

• The first $n$ terms of $f$ are $f=\{2,10,5,8,7\}$.

• The first $n$ terms of $g$ are $g=\{1,8,3,5,4\}$.

So the final answer is $(1-2)\times(8-10)\times(3-5)\times(5-8)\times(4-7)=-36$, and the result modulo $998244353$ is $998244317$.

---

Constraints

For $40\%$ of the testdata, $n \le 100$.

For another $10\%$ of the testdata, each query satisfies $A=B,X=Y$.

For another $10\%$ of the testdata, $T=1$.

For $100\%$ of the testdata, $1 \le A,B,X,Y,n \le 10^9$ and $1 \le T \le 5\times 10^4$.

Translated by ChatGPT 5