Description

小花某天给了你一个仅由数字、字母和三种括号组成的压缩字符串 S。请你按如下规则将字符串展开，并输出展开完毕的字符串中第 K 个字符。

Step 1：找到一对括号，中间不含有任何其他括号。当找到的这对括号：

（1）如果为小括号 ()，则将里面的内容重复 $n$ 遍，$n$ 为左括号后面紧挨着的数字（$1 \leq n \leq 9$）。

（2）如果为中括号 []，则将里面的字母进行大小写转换。

（3）如果为大括号，则将里面的内容进行翻转。例如 $\{abcd\}=dcba$。

Step 2：将 Step 1 中的那一对括号删除。

Step 3：回到 Step 1 重复操作，直到字符串不包含任何括号。

Format

Input

第一行为整数 $T$，表示数据组数。

接下来 $T$ 行，每行一个字符串 $S$ 和相应的整数 $P$，描述一组数据。字符串保证仅由大小写字母、小括号()、中括号[]、大括号{}以及数字组成。

Output

一个长度为 $T$ 的字符串，其中第 $i$ 个字符描述输入中第 $i$ 组数据的处理结果。

Samples

2
{Once[Again]} 3
(2[{code}]) 8

AC

input2

见样例文件 ex.in。

output2

见样例文件 ex.out。

Constraints

设括号嵌套层数为 $l$，原字符串长度为 $n$，展开后字符串长度为 $m$。

对于 $20\%$ 的数据，保证 $1 \leq l \leq 100$，$1 \leq n,m \leq 10^3$ 且只含有一种括号。

对于 $50\%$ 的数据，保证 $1 \leq l \leq 10^3$，$1 \leq n,m \leq 10^4$。

对于 $100\%$ 的数据，保证 $1 \leq T \leq 10$，$1 \leq l \leq 5 \times 10^4$，$1 \leq n,m \leq 5 \times 10^5$，数据保证合法。