apaz/codeforces-genesys huggingface dataset:
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a multiset (i. e. a set that can contain multiple equal integers) containing $$$2n$$$ integers. Determine if you can split it into exactly $$$n$$$ pairs (i. e. each element should be in exactly one pair) so that the sum of the two elements in each pair is odd (i. e. when divided by $$$2$$$, the remainder is $$$1$$$).

## Input Format
The input consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1\leq t\leq 100$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains an integer $$$n$$$ ($$$1\leq n\leq 100$$$).

The second line of each test case contains $$$2n$$$ integers $$$a_1,a_2,\dots, a_{2n}$$$ ($$$0\leq a_i\leq 100$$$) — the numbers in the set.

## Output Format
For each test case, print "Yes" if it can be split into exactly $$$n$$$ pairs so that the sum of the two elements in each pair is odd, and "No" otherwise. You can print each letter in any case.

## Examples
```input
5
2
2 3 4 5
3
2 3 4 5 5 5
1
2 4
1
2 3
4
1 5 3 2 6 7 3 4
```
```output
Yes
No
No
Yes
No
```

## Note
In the first test case, a possible way of splitting the set is $$$(2,3)$$$, $$$(4,5)$$$.

In the second, third and fifth test case, we can prove that there isn't any possible way.

In the fourth test case, a possible way of splitting the set is $$$(2,3)$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 3.0 seconds
Memory limit: 512.0 MB

# Problem
There is an infinite set generated as follows:

- $$$1$$$ is in this set.
- If $$$x$$$ is in this set, $$$x \cdot a$$$ and $$$x+b$$$ both are in this set.

For example, when $$$a=3$$$ and $$$b=6$$$, the five smallest elements of the set are:

- $$$1$$$,
- $$$3$$$ ($$$1$$$ is in this set, so $$$1\cdot a=3$$$ is in this set),
- $$$7$$$ ($$$1$$$ is in this set, so $$$1+b=7$$$ is in this set),
- $$$9$$$ ($$$3$$$ is in this set, so $$$3\cdot a=9$$$ is in this set),
- $$$13$$$ ($$$7$$$ is in this set, so $$$7+b=13$$$ is in this set).

Given positive integers $$$a$$$, $$$b$$$, $$$n$$$, determine if $$$n$$$ is in this set.

## Input Format
The input consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1\leq t\leq 10^5$$$) — the number of test cases. The description of the test cases follows.

The only line describing each test case contains three integers $$$n$$$, $$$a$$$, $$$b$$$ ($$$1\leq n,a,b\leq 10^9$$$) separated by a single space.

## Output Format
For each test case, print "Yes" if $$$n$$$ is in this set, and "No" otherwise. You can print each letter in any case.

## Examples
```input
5
24 3 5
10 3 6
2345 1 4
19260817 394 485
19260817 233 264
```
```output
Yes
No
Yes
No
Yes
```

## Note
In the first test case, $$$24$$$ is generated as follows:

- $$$1$$$ is in this set, so $$$3$$$ and $$$6$$$ are in this set;
- $$$3$$$ is in this set, so $$$9$$$ and $$$8$$$ are in this set;
- $$$8$$$ is in this set, so $$$24$$$ and $$$13$$$ are in this set.

Thus we can see $$$24$$$ is in this set.

The five smallest elements of the set in the second test case is described in statements. We can see that $$$10$$$ isn't among them.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Let $$$f(i)$$$ denote the minimum positive integer $$$x$$$ such that $$$x$$$ is not a divisor of $$$i$$$.

Compute $$$\sum_{i=1}^n f(i)$$$ modulo $$$10^9+7$$$. In other words, compute $$$f(1)+f(2)+\dots+f(n)$$$ modulo $$$10^9+7$$$.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1\leq t\leq 10^4$$$), the number of test cases. Then $$$t$$$ cases follow.

The only line of each test case contains a single integer $$$n$$$ ($$$1\leq n\leq 10^{16}$$$).

## Output Format
For each test case, output a single integer $$$ans$$$, where $$$ans=\sum_{i=1}^n f(i)$$$ modulo $$$10^9+7$$$.

## Examples
```input
6
1
2
3
4
10
10000000000000000
```
```output
2
5
7
10
26
366580019
```

## Note
In the fourth test case $$$n=4$$$, so $$$ans=f(1)+f(2)+f(3)+f(4)$$$.

- $$$1$$$ is a divisor of $$$1$$$ but $$$2$$$ isn't, so $$$2$$$ is the minimum positive integer that isn't a divisor of $$$1$$$. Thus, $$$f(1)=2$$$.
- $$$1$$$ and $$$2$$$ are divisors of $$$2$$$ but $$$3$$$ isn't, so $$$3$$$ is the minimum positive integer that isn't a divisor of $$$2$$$. Thus, $$$f(2)=3$$$.
- $$$1$$$ is a divisor of $$$3$$$ but $$$2$$$ isn't, so $$$2$$$ is the minimum positive integer that isn't a divisor of $$$3$$$. Thus, $$$f(3)=2$$$.
- $$$1$$$ and $$$2$$$ are divisors of $$$4$$$ but $$$3$$$ isn't, so $$$3$$$ is the minimum positive integer that isn't a divisor of $$$4$$$. Thus, $$$f(4)=3$$$.

Therefore, $$$ans=f(1)+f(2)+f(3)+f(4)=2+3+2+3=10$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 3.0 seconds
Memory limit: 512.0 MB

# Problem
You are given a sequence $$$A$$$, where its elements are either in the form + x or -, where $$$x$$$ is an integer.

For such a sequence $$$S$$$ where its elements are either in the form + x or -, define $$$f(S)$$$ as follows:

- iterate through $$$S$$$'s elements from the first one to the last one, and maintain a multiset $$$T$$$ as you iterate through it.
- for each element, if it's in the form + x, add $$$x$$$ to $$$T$$$; otherwise, erase the smallest element from $$$T$$$ (if $$$T$$$ is empty, do nothing).
- after iterating through all $$$S$$$'s elements, compute the sum of all elements in $$$T$$$. $$$f(S)$$$ is defined as the sum.

The sequence $$$b$$$ is a subsequence of the sequence $$$a$$$ if $$$b$$$ can be derived from $$$a$$$ by removing zero or more elements without changing the order of the remaining elements. For all $$$A$$$'s subsequences $$$B$$$, compute the sum of $$$f(B)$$$, modulo $$$998\,244\,353$$$.

## Input Format
The first line contains an integer $$$n$$$ ($$$1\leq n\leq 500$$$) — the length of $$$A$$$.

Each of the next $$$n$$$ lines begins with an operator + or -. If the operator is +, then it's followed by an integer $$$x$$$ ($$$1\le x<998\,244\,353$$$). The $$$i$$$-th line of those $$$n$$$ lines describes the $$$i$$$-th element in $$$A$$$.

## Output Format
Print one integer, which is the answer to the problem, modulo $$$998\,244\,353$$$.

## Examples
```input
4
-
+ 1
+ 2
-
```
```output
16
```
-----
```input
15
+ 2432543
-
+ 4567886
+ 65638788
-
+ 578943
-
-
+ 62356680
-
+ 711111
-
+ 998244352
-
-
```
```output
750759115
```

## Note
In the first example, the following are all possible pairs of $$$B$$$ and $$$f(B)$$$:

- $$$B=$$$ {}, $$$f(B)=0$$$.
- $$$B=$$$ {-}, $$$f(B)=0$$$.
- $$$B=$$$ {+ 1, -}, $$$f(B)=0$$$.
- $$$B=$$$ {-, + 1, -}, $$$f(B)=0$$$.
- $$$B=$$$ {+ 2, -}, $$$f(B)=0$$$.
- $$$B=$$$ {-, + 2, -}, $$$f(B)=0$$$.
- $$$B=$$$ {-}, $$$f(B)=0$$$.
- $$$B=$$$ {-, -}, $$$f(B)=0$$$.
- $$$B=$$$ {+ 1, + 2}, $$$f(B)=3$$$.
- $$$B=$$$ {+ 1, + 2, -}, $$$f(B)=2$$$.
- $$$B=$$$ {-, + 1, + 2}, $$$f(B)=3$$$.
- $$$B=$$$ {-, + 1, + 2, -}, $$$f(B)=2$$$.
- $$$B=$$$ {-, + 1}, $$$f(B)=1$$$.
- $$$B=$$$ {+ 1}, $$$f(B)=1$$$.
- $$$B=$$$ {-, + 2}, $$$f(B)=2$$$.
- $$$B=$$$ {+ 2}, $$$f(B)=2$$$.

The sum of these values is $$$16$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 512.0 MB

# Problem
This is the easy version of the problem. The only difference between the easy version and the hard version is the constraints on $$$n$$$. You can only make hacks if both versions are solved.

A permutation of $$$1, 2, \ldots, n$$$ is a sequence of $$$n$$$ integers, where each integer from $$$1$$$ to $$$n$$$ appears exactly once. For example, $$$[2,3,1,4]$$$ is a permutation of $$$1, 2, 3, 4$$$, but $$$[1,4,2,2]$$$ isn't because $$$2$$$ appears twice in it.

Recall that the number of inversions in a permutation $$$a_1, a_2, \ldots, a_n$$$ is the number of pairs of indices $$$(i, j)$$$ such that $$$i < j$$$ and $$$a_i > a_j$$$.

Let $$$p$$$ and $$$q$$$ be two permutations of $$$1, 2, \ldots, n$$$. Find the number of permutation pairs $$$(p,q)$$$ that satisfy the following conditions:

- $$$p$$$ is lexicographically smaller than $$$q$$$.
- the number of inversions in $$$p$$$ is greater than the number of inversions in $$$q$$$.

Print the number of such pairs modulo $$$mod$$$. Note that $$$mod$$$ may not be a prime.

## Input Format
The only line contains two integers $$$n$$$ and $$$mod$$$ ($$$1\le n\le 50$$$, $$$1\le mod\le 10^9$$$).

## Output Format
Print one integer, which is the answer modulo $$$mod$$$.

## Examples
```input
4 403458273
```
```output
17
```

## Note
The following are all valid pairs $$$(p,q)$$$ when $$$n=4$$$.

- $$$p=[1,3,4,2]$$$, $$$q=[2,1,3,4]$$$,
- $$$p=[1,4,2,3]$$$, $$$q=[2,1,3,4]$$$,
- $$$p=[1,4,3,2]$$$, $$$q=[2,1,3,4]$$$,
- $$$p=[1,4,3,2]$$$, $$$q=[2,1,4,3]$$$,
- $$$p=[1,4,3,2]$$$, $$$q=[2,3,1,4]$$$,
- $$$p=[1,4,3,2]$$$, $$$q=[3,1,2,4]$$$,
- $$$p=[2,3,4,1]$$$, $$$q=[3,1,2,4]$$$,
- $$$p=[2,4,1,3]$$$, $$$q=[3,1,2,4]$$$,
- $$$p=[2,4,3,1]$$$, $$$q=[3,1,2,4]$$$,
- $$$p=[2,4,3,1]$$$, $$$q=[3,1,4,2]$$$,
- $$$p=[2,4,3,1]$$$, $$$q=[3,2,1,4]$$$,
- $$$p=[2,4,3,1]$$$, $$$q=[4,1,2,3]$$$,
- $$$p=[3,2,4,1]$$$, $$$q=[4,1,2,3]$$$,
- $$$p=[3,4,1,2]$$$, $$$q=[4,1,2,3]$$$,
- $$$p=[3,4,2,1]$$$, $$$q=[4,1,2,3]$$$,
- $$$p=[3,4,2,1]$$$, $$$q=[4,1,3,2]$$$,
- $$$p=[3,4,2,1]$$$, $$$q=[4,2,1,3]$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 4.0 seconds
Memory limit: 512.0 MB

# Problem
This is the hard version of the problem. The only difference between the easy version and the hard version is the constraints on $$$n$$$. You can only make hacks if both versions are solved.

A permutation of $$$1, 2, \ldots, n$$$ is a sequence of $$$n$$$ integers, where each integer from $$$1$$$ to $$$n$$$ appears exactly once. For example, $$$[2,3,1,4]$$$ is a permutation of $$$1, 2, 3, 4$$$, but $$$[1,4,2,2]$$$ isn't because $$$2$$$ appears twice in it.

Recall that the number of inversions in a permutation $$$a_1, a_2, \ldots, a_n$$$ is the number of pairs of indices $$$(i, j)$$$ such that $$$i < j$$$ and $$$a_i > a_j$$$.

Let $$$p$$$ and $$$q$$$ be two permutations of $$$1, 2, \ldots, n$$$. Find the number of permutation pairs $$$(p,q)$$$ that satisfy the following conditions:

- $$$p$$$ is lexicographically smaller than $$$q$$$.
- the number of inversions in $$$p$$$ is greater than the number of inversions in $$$q$$$.

Print the number of such pairs modulo $$$mod$$$. Note that $$$mod$$$ may not be a prime.

## Input Format
The only line contains two integers $$$n$$$ and $$$mod$$$ ($$$1\le n\le 500$$$, $$$1\le mod\le 10^9$$$).

## Output Format
Print one integer, which is the answer modulo $$$mod$$$.

## Examples
```input
4 403458273
```
```output
17
```

## Note
The following are all valid pairs $$$(p,q)$$$ when $$$n=4$$$.

- $$$p=[1,3,4,2]$$$, $$$q=[2,1,3,4]$$$,
- $$$p=[1,4,2,3]$$$, $$$q=[2,1,3,4]$$$,
- $$$p=[1,4,3,2]$$$, $$$q=[2,1,3,4]$$$,
- $$$p=[1,4,3,2]$$$, $$$q=[2,1,4,3]$$$,
- $$$p=[1,4,3,2]$$$, $$$q=[2,3,1,4]$$$,
- $$$p=[1,4,3,2]$$$, $$$q=[3,1,2,4]$$$,
- $$$p=[2,3,4,1]$$$, $$$q=[3,1,2,4]$$$,
- $$$p=[2,4,1,3]$$$, $$$q=[3,1,2,4]$$$,
- $$$p=[2,4,3,1]$$$, $$$q=[3,1,2,4]$$$,
- $$$p=[2,4,3,1]$$$, $$$q=[3,1,4,2]$$$,
- $$$p=[2,4,3,1]$$$, $$$q=[3,2,1,4]$$$,
- $$$p=[2,4,3,1]$$$, $$$q=[4,1,2,3]$$$,
- $$$p=[3,2,4,1]$$$, $$$q=[4,1,2,3]$$$,
- $$$p=[3,4,1,2]$$$, $$$q=[4,1,2,3]$$$,
- $$$p=[3,4,2,1]$$$, $$$q=[4,1,2,3]$$$,
- $$$p=[3,4,2,1]$$$, $$$q=[4,1,3,2]$$$,
- $$$p=[3,4,2,1]$$$, $$$q=[4,2,1,3]$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a digital clock with $$$n$$$ digits. Each digit shows an integer from $$$0$$$ to $$$9$$$, so the whole clock shows an integer from $$$0$$$ to $$$10^n-1$$$. The clock will show leading zeroes if the number is smaller than $$$10^{n-1}$$$.

You want the clock to show $$$0$$$ with as few operations as possible. In an operation, you can do one of the following:

- decrease the number on the clock by $$$1$$$, or
- swap two digits (you can choose which digits to swap, and they don't have to be adjacent).

Your task is to determine the minimum number of operations needed to make the clock show $$$0$$$.

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^3$$$).

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 100$$$) — number of digits on the clock.

The second line of each test case contains a string of $$$n$$$ digits $$$s_1, s_2, \ldots, s_n$$$ ($$$0 \le s_1, s_2, \ldots, s_n \le 9$$$) — the number on the clock.

Note: If the number is smaller than $$$10^{n-1}$$$ the clock will show leading zeroes.

## Output Format
For each test case, print one integer: the minimum number of operations needed to make the clock show $$$0$$$.

## Examples
```input
7
3
007
4
1000
5
00000
3
103
4
2020
9
123456789
30
001678294039710047203946100020
```
```output
7
2
0
5
6
53
115
```

## Note
In the first example, it's optimal to just decrease the number $$$7$$$ times.

In the second example, we can first swap the first and last position and then decrease the number by $$$1$$$.

In the third example, the clock already shows $$$0$$$, so we don't have to perform any operations.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are given two arrays $$$a$$$ and $$$b$$$ of length $$$n$$$. Array $$$a$$$ contains each odd integer from $$$1$$$ to $$$2n$$$ in an arbitrary order, and array $$$b$$$ contains each even integer from $$$1$$$ to $$$2n$$$ in an arbitrary order.

You can perform the following operation on those arrays:

- choose one of the two arrays
- pick an index $$$i$$$ from $$$1$$$ to $$$n-1$$$
- swap the $$$i$$$-th and the $$$(i+1)$$$-th elements of the chosen array

For two different arrays $$$x$$$ and $$$y$$$ of the same length $$$n$$$, we say that $$$x$$$ is lexicographically smaller than $$$y$$$ if in the first position where $$$x$$$ and $$$y$$$ differ, the array $$$x$$$ has a smaller element than the corresponding element in $$$y$$$.

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$).

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the length of the arrays.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 2n$$$, all $$$a_i$$$ are odd and pairwise distinct) — array $$$a$$$.

The third line of each test case contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le 2n$$$, all $$$b_i$$$ are even and pairwise distinct) — array $$$b$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

## Output Format
For each test case, print one integer: the minimum number of operations needed to make array $$$a$$$ lexicographically smaller than array $$$b$$$.

We can show that an answer always exists.

## Examples
```input
3
2
3 1
4 2
3
5 3 1
2 4 6
5
7 5 9 1 3
2 4 6 10 8
```
```output
0
2
3
```

## Note
In the first example, the array $$$a$$$ is already lexicographically smaller than array $$$b$$$, so no operations are required.

In the second example, we can swap $$$5$$$ and $$$3$$$ and then swap $$$2$$$ and $$$4$$$, which results in $$$[3, 5, 1]$$$ and $$$[4, 2, 6]$$$. Another correct way is to swap $$$3$$$ and $$$1$$$ and then swap $$$5$$$ and $$$1$$$, which results in $$$[1, 5, 3]$$$ and $$$[2, 4, 6]$$$. Yet another correct way is to swap $$$4$$$ and $$$6$$$ and then swap $$$2$$$ and $$$6$$$, which results in $$$[5, 3, 1]$$$ and $$$[6, 2, 4]$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Luntik has decided to try singing. He has $$$a$$$ one-minute songs, $$$b$$$ two-minute songs and $$$c$$$ three-minute songs. He wants to distribute all songs into two concerts such that every song should be included to exactly one concert.

He wants to make the absolute difference of durations of the concerts as small as possible. The duration of the concert is the sum of durations of all songs in that concert.

Please help Luntik and find the minimal possible difference in minutes between the concerts durations.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.

Each test case consists of one line containing three integers $$$a, b, c$$$ $$$(1 \le a, b, c \le 10^9)$$$ — the number of one-minute, two-minute and three-minute songs.

## Output Format
For each test case print the minimal possible difference in minutes between the concerts durations.

## Examples
```input
4
1 1 1
2 1 3
5 5 5
1 1 2
```
```output
0
1
0
1
```

## Note
In the first test case, Luntik can include a one-minute song and a two-minute song into the first concert, and a three-minute song into the second concert. Then the difference will be equal to $$$0$$$.

In the second test case, Luntik can include two one-minute songs and a two-minute song and a three-minute song into the first concert, and two three-minute songs into the second concert. The duration of the first concert will be $$$1 + 1 + 2 + 3 = 7$$$, the duration of the second concert will be $$$6$$$. The difference of them is $$$|7-6| = 1$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Luntik came out for a morning stroll and found an array $$$a$$$ of length $$$n$$$. He calculated the sum $$$s$$$ of the elements of the array ($$$s= \sum_{i=1}^{n} a_i$$$). Luntik calls a subsequence of the array $$$a$$$ nearly full if the sum of the numbers in that subsequence is equal to $$$s-1$$$.

Luntik really wants to know the number of nearly full subsequences of the array $$$a$$$. But he needs to come home so he asks you to solve that problem!

A sequence $$$x$$$ is a subsequence of a sequence $$$y$$$ if $$$x$$$ can be obtained from $$$y$$$ by deletion of several (possibly, zero or all) elements.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases. The next $$$2 \cdot t$$$ lines contain descriptions of test cases. The description of each test case consists of two lines.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 60$$$) — the length of the array.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — the elements of the array $$$a$$$.

## Output Format
For each test case print the number of nearly full subsequences of the array.

## Examples
```input
5
5
1 2 3 4 5
2
1000 1000
2
1 0
5
3 0 2 1 1
5
2 1 0 3 0
```
```output
1
0
2
4
4
```

## Note
In the first test case, $$$s=1+2+3+4+5=15$$$, only $$$(2,3,4,5)$$$ is a nearly full subsequence among all subsequences, the sum in it is equal to $$$2+3+4+5=14=15-1$$$.

In the second test case, there are no nearly full subsequences.

In the third test case, $$$s=1+0=1$$$, the nearly full subsequences are $$$(0)$$$ and $$$()$$$ (the sum of an empty subsequence is $$$0$$$).

Now solve the problem and return the code.