题目描述

你一定在各类社交平台或短视频软件上刷到过这样让人血压升高的游戏广告：玩家操控的角色顶着一个极其可怜的战斗力数值，面对战斗力「$\times 10$」和「$\div 2$」两扇门，偏偏毫不犹豫地走向了「$\div 2$」，最后遇到高等级的怪物被无情击败。

每次看到这种视频，你都恨不得冲进屏幕替他操作。现在，你终于下载到了这款名为《公式战士（Formula Warriors）》的游戏，你决定亲自上手，打破游戏广告的弱智操作，向所有人展示什么才是真正的最强战士。

初始时，你控制的战士战斗力为一个正整数 $x$。

游戏共有 $n$ 个关卡。在每个关卡中，战士的面前会出现 $2$ 扇门，战士必须且只能选择其中一扇门通过。

每一扇门上都写有一个公式，当战士通过这扇门时，战士的战斗力 $x$ 会变为：

$$x \leftarrow \lfloor\text{Expression1} \ \ \text{Operator} \ \ \text{Expression2}\rfloor$$

其中：

• $\text{Operator}$ 为加（$+$）、减（$-$）、乘（$\times$）、除（$\div$）四种运算符中的一种；
• 在 $\text{Expression1}$ 和 $\text{Expression2}$ 中，恰有一个是战士当前的战斗力 $x$，恰有一个是门上给定的正整数常量 $v$；
• $\lfloor A \rfloor$ 表示对 $A$ 向下取整。

保证不论你在游戏中做出何种合法的选择，在完成第 $i$（$1\le i\le n$）次操作后，战士当前的战斗力 $x$ 始终满足 $1\le x\le 10^{18}$。

你需要合理规划这 $n$ 次选择，使得 $n$ 个关卡全部通过后，最终战士的战斗力 $x$ 被最大化。请输出这个可能的最大战斗力。

输入格式

本题包含多组测试用例。输入的第一行，包含一个正整数 $T$（$1\le T\le 10^3$），表示测试用例的数量。

接下来是 $T$ 组测试用例的描述。

每个测试用例的第一行，包含两个正整数 $n$ 和 $x$（$1\le n\le 10^4$，$1\le x\le 10^{18}$），用一个空格分隔，分别表示关卡数量和战士的初始战斗力。

接下来 $n$ 行，第 $i$ 行表示第 $i$ 个关卡的 $2$ 扇门上的公式信息，包含 $6$ 个以一个空格分隔的元素，前 $3$ 个元素描述第一扇门，后 $3$ 个元素描述第二扇门。

对于每一扇门，其给定的 $3$ 个元素格式严格为 $\text{Expression1} \ \ \text{Operator} \ \ \text{Expression2}$，其中：

• $\text{Operator}$ 为字符 $\texttt{+}$，$\texttt{-}$，$\texttt{*}$，$\texttt{/}$ 中的一种，分别代表加、减、乘、除；
• $\text{Expression1}$ 和 $\text{Expression2}$ 中，恰有一个是字符 $\texttt{x}$，代表玩家当前战斗力；恰有一个是正整数 $v$（$1\le v\le 10^{18}$），代表门上给定的常量。

例如，$\texttt{x + 5}$ 表示将战斗力变为 $\lfloor x + 5 \rfloor$；$\texttt{100 / x}$ 表示将战斗力变为 $\lfloor 100 \div x \rfloor$。

保证不论你在游戏中做出何种合法的选择，在完成第 $i$（$1\le i\le n$）次操作后，战士当前的战斗力 $x$ 始终满足 $1\le x\le 10^{18}$。

保证所有测试用例中 $n$ 的总和不超过 $10^4$。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示战士通过 $n$ 个关卡后，战士能获得的最大战斗力。

2
3 2
x + 3 x * 2
100 / x x * 10
x - 10 1000 / x
1 1145141919810
1145141919810 + x 3 * x

50
3435425759430

提示

在样例测试用例 1 中，一种最优的选择方案为：第一扇门 $\to$ 第一扇门 $\to$ 第二扇门。

对应的战斗力的变化为：$2 \to 5 \to 20 \to 50$。