E. Bracket Dance
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

You have finally reached the treasure! Of course, it is a string $$$s$$$ of length $$$n=2^k$$$, consisting of brackets.

To be straightforward — cat Persik$$$\text{}^\dagger$$$ loves bracket sequences and powers of two!

Persik plays with the string $$$s$$$ — several times (possibly zero) he divides it into parts and assembles it back.

In one step, the following occurs:

The sequence is divided into blocks of length $$$m = 2^x$$$ $$$(x \ge 1)$$$, each block is split into two halves, and the halves within the block are swapped.

Example:

$$$x = 2, m = 4, s = (()) \Rightarrow |((\cdot))| \Rightarrow |))\cdot((| \Rightarrow ))(($$$

$$$x = 2, m = 4, s = ((()))() \Rightarrow |((\cdot()|))\cdot()| \Rightarrow |()\cdot((|()\cdot))| \Rightarrow ()((()))$$$

$$$x = 1, m = 2, s = ((()))() \Rightarrow |(\cdot(|(\cdot)|)\cdot)|(\cdot)| \Rightarrow |(\cdot(|)\cdot(|)\cdot)|)\cdot(| \Rightarrow (()()))($$$

We are interested in when Persik will get tired of playing (i.e., when he gets bored of changing the original string) — to do this, help us find out (depending on the type of query):

  1. How many different ways are there to obtain a valid bracket sequence$$$^\ddagger$$$ (VBS) from the original string $$$s$$$ while Persik plays with it. Two ways are considered different if for some $$$i$$$ the character originally at position $$$i$$$ has moved to different positions in these two ways.
  2. How many different VBS can be obtained from the original string. Two VBS $$$a, b$$$ are considered different if there exists an index $$$i$$$ such that $$$a_i \ne b_i$$$.

$$$^\dagger \text{}$$$ Persik is a shark in the world of programming.

$$$^\ddagger$$$ A bracket sequence is called valid if it can be turned into a correct mathematical expression by adding only the symbols $$$+$$$ and $$$1$$$. For example, the sequences $$$(())(), (), (()(()))$$$ and the empty string are valid, while $$$)(, (()$$$ and $$$(()))($$$ are not.

Input

The first line contains a single number $$$T$$$ — the number of test cases $$$(1 \le T \le 10\,000)$$$.

The second line contains a single number $$$Q$$$ — the type of query (common for all test cases) $$$(1 \le Q \le 2)$$$.

In the following $$$T$$$ lines, one bracket sequence is given per line. $$$(2 \le |s_i| \le 2^{22})$$$.

The total length of all input sequences does not exceed $$$2^{22}$$$ $$$(\sum_{i = 1}^T |s_i| \le 2^{22})$$$.

Output

For each string, output the required number:

For $$$Q = 1$$$ — the number of different permutations such that the resulting string is a VBS.

For $$$Q = 2$$$ — the number of different VBS that can be obtained through such actions.

Scoring
GroupPoints Additional Constraints Required Groups
118$$$q = 1$$$, $$$\sum_{i = 1}^T |s_i| \le 2^8$$$–
226$$$q = 1$$$, $$$\sum_{i = 1}^T |s_i| \le 2^{14}$$$1
326$$$q = 1$$$, $$$\sum_{i = 1}^T |s_i| \le 2^{22}$$$1, 2
413$$$q = 2$$$, $$$\sum_{i = 1}^T |s_i| \le 2^{12}$$$–
517$$$q = 2$$$, $$$\sum_{i = 1}^T |s_i| \le 2^{17}$$$4
Examples
Input
2
1
))((
((()))()
Output
2
2
Input
2
2
))((
((()))()
Output
1
2
Note

If you take the string $$$s = (^1(^2)^3)^4$$$ (with the original position indicated after each symbol), it is itself a VBS, and also after one step with $$$x = 1, m = 2$$$ we get the string $$$(^2(^1)^4)^3$$$. In total, there are two options.

The illustration shows the application of one step $$$x = 2, m = 4$$$ to the string $$$((()))()$$$.

Illustration for the example