Description

  Playing badminton on a wild court, on a campus with a good ecosystem, often runs into accidents—

  "Tianyi! Why is the shuttlecock stuck in the tree again!"

  Just as A Ling saw, their only remaining poor shuttlecock was swung by Tianyi onto the tree with the strength she uses to eat buns. To avoid the awkwardness of borrowing someone else’s volleyball or basketball to hit the tree, A Ling specially prepared a folding pole this time.

  The folding pole is initially fully retracted, and we consider its length to be $\ell=0$. Fully extending the folding pole takes $n$ steps, and each step is one of the following two cases:

1. Unfold the folding joint at the end of the pole. This operation has no extra parameters. After the operation, $\ell\gets 2\ell$, i.e. the pole’s length becomes twice the original.

2. Extend the telescopic joint at the end of the pole. This operation provides an additional variable parameter $d$. After the operation, $\ell\gets \ell+d$, i.e. the pole’s length increases by $d$.

  The height of the shuttlecock in the tree, the final height of the pole, and Tianyi’s bun-eating strength may all be huge, so A Ling needs you to help compute the final length $\ell$ of the pole. You need to answer, after the $n$ operations are completed in order, the binary representation of $\ell$.

Input Format

The first line contains an integer $T$, indicating the number of test cases you need to process.

For each test case:

• The first line contains an integer $n$, indicating the number of operations to be performed.

• The next $n$ lines each have the format 1 or 2 d, describing the two types of operations respectively. The integer $d$ is given in decimal.

Output Format

For each test case, output the binary representation of the final $\ell$. Your answer should not contain extra leading zeros.

2
2
1
2 0
5
1
2 1
2 2
1
2 6

0
1100

Hint

Explanation of Sample #1

For the first test case: the change process of $\ell$ is $0 \rightarrow 0 \rightarrow 0$, and $(0)_{10}=(0)_2$.

For the second test case: the change process of $\ell$ is $0 \rightarrow 0 \rightarrow 1 \rightarrow 3 \rightarrow 6 \rightarrow 12$, and $(12)_{10}=(1100)_2$.

Constraints

For $100\%$ of the data, $1\leq T \leq 5$, $1\leq n \leq 10^5$, $0\leq d < 2^{16}$.

For different subtasks, the constraints are as follows:

• Special Property: only the second type of operation exists.

Translated by ChatGPT 5