考虑以下游戏。
在这个游戏中,一个关卡由 $$$n$$$ 对门组成。每对包含一个左门和一个右门。每个门执行以下两个操作之一:
- 加法运算 (+ 一个):将车道中的人数增加恒定量$$$a$$$。
- 乘法运算 (x 一个):将车道中的当前人数乘以整数 $$$a$$$。这意味着该车道上的人数增加了 $$$(a - 1)$$$ 乘以当前人数。
每次行动获得的额外人员可以分配到任一车道。然而,人们已经在巷子里 不能 被移动到另一条车道。
最初,每条车道上有一个人。您的任务是确定关卡结束时可以达到的最大总人数。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \le 30$$$) — 门对的数量。
每个测试用例的接下来 $$$n$$$ 行提供每个门对中左门和右门的信息。每个门的信息以以下形式给出 + $$$a$$$ ($$$1 \le a \le 1000$$$) 或 x $$$a$$$ ($$$2 \le a \le 3$$$) 对于某个整数 $$$a$$$。
输出
对于每个测试用例,输出一个整数 - 关卡结束时的最大总人数。
示例
输入复制
43+ 4 x 2x 3 x 3+ 7 + 44+ 9 x 2x 2 x 3+ 9 + 10x 2 + 14x 2 + 1+ 9 + 10x 2 x 3+ 9 x 25x 3 x 3x 2 x 2+ 21 + 2x 2 x 3+ 41 x 3
输出复制
32 98 144 351
注意
在第一种情况下,这是一种最佳地玩这个游戏的可能方法。
最初,我们在左车道上有 $$$l=1$$$ 人,在右车道上有 $$$r=1$$$ 人。
通过第一对门后,我们从左门获得 $$$4$$$ 人,从右门获得 $$$1 \cdot (2-1) = 1$$$ 人,总共 $$$4+1=5$$$ 人。我们将 $$$2$$$ 人分配到左车道,将 $$$3$$$ 人分配到右车道。这导致左车道上有 $$$l=1+2=3$$$ 人,右车道上有 $$$r=1+3=4$$$ 人。
通过第二对大门后,我们从左门获得 $$$3 \cdot (3-1) = 6$$$ 人,从右门获得 $$$4 \cdot (3-1) = 8$$$ 人,总共 $$$6+8=14$$$ 人。我们将 $$$7$$$ 人分配到左车道,将 $$$7$$$ 人分配到右车道。这导致左车道上有 $$$l=3+7=10$$$ 人,右车道上有 $$$r=4+7=11$$$ 人。
穿过最后一对门后,我们从左门获得$$$7$$$人,从右门获得$$$4$$$人,总共$$$7+4=11$$$人。我们将 $$$6$$$ 人分配到左车道,将 $$$5$$$ 人分配到右车道。这导致左车道上有 $$$l=10+6=16$$$ 人,右车道上有 $$$r=11+5=16$$$ 人。
最后总人数为$$$16+16=32$$$。