There are ~n~ bamboo sticks with lengths ~a_1, a_2, \ldots, a_n~ as positive integers. You are allowed to perform the following operation zero or multiple times:

• Choose any stick, break it into two smaller sticks with positive integer lengths, such that the two new sticks have unequal lengths.

After performing the operation, you use the sticks to form pairs of chopsticks. A pair of chopsticks is formed from two sticks with equal lengths. Find the maximum number of pairs of chopsticks that can be formed after performing the operation.

Input

The input consists of multiple test cases. The first line of the input contains a positive integer ~t~ (~1 \le t \le 10\,000~) which is the number of test cases. The description of each test case is as follows.

The first line contains an integer ~n~ (~1 \le n \le 2 \cdot 10^5~) — the number of bamboo sticks.

The second line contains ~n~ integers ~a_1, a_2, \ldots, a_n~ (~1 \le a_i \le 10^9~) — the lengths of the bamboo sticks.

The sum of ~n~ in all test cases is guaranteed not to exceed ~2 \cdot 10^5~.

Output

For each test case, output a single integer denoting the maximum number of pairs of chopsticks that can be formed.

Scoring

Sample Input 1

2
7
1 1 1 2 2 2 2
4
2 3 3 2

Sample Output 1

3
3

Sample Input 2

2
1
4
10
3 1 4 1 5 9 2 6 5 3

Sample Output 2

1
15

Notes

In the first test case in the first example, we have ~3~ bamboo sticks of length ~1~, and ~4~ bamboo sticks of length ~2~. We cannot break any stick into two smaller sticks with different lengths. From these sticks, we can create ~1~ pair of chopsticks from two sticks of length ~1~, and add ~2~ more pairs from the sticks of length ~2~. Thus, the maximum number of pairs of chopsticks that can be formed is ~1 + 2 = 3~.

Note that there is one stick of length ~1~ left unused.

In the second test case in the first example, we can break the stick of length ~3~ into two smaller sticks of length ~1~ and ~2~. Thus, we will have ~1~ pair of chopsticks from the stick of length ~1~, and ~2~ pairs from the stick of length ~2~. Therefore, we still obtain ~1 + 2 = 3~ pairs of chopsticks.

In the first test case in the second example, we have only one bamboo stick of length ~4~. Initially, we can break this stick into sticks of length ~1~ and ~3~. Then we can break the stick of length ~3~ into sticks of length ~1~ and ~2~. From here, we can create a pair of chopsticks from two sticks of length ~1~.

You are playing the most popular MMO game at the moment. The in-game currency is gems, divided into ~n~ levels. Currently, you have ~a_i~ gems at level ~i~. To buy the most expensive equipment in the game, you need to pay ~b_i~ gems at level ~i~.

The game has a gem exchange system that allows you to:

• Exchange ~2~ gems at level ~i~ for ~1~ gem at level ~i+1~ (with ~1 \le i < n~).

• Exchange ~1~ gem at level ~i~ for ~2~ gems at level ~i-1~ (with ~1 < i \le n~).

Determine if there is any way to exchange gems to have enough gems at each level to buy the equipment using zero or many exchanges.

Input

The input consists of multiple test cases. The first line of the input contains a positive integer ~t~ (~1 \le t \le 10\,000~) which is the number of test cases. The description of each test case is as follows.

The first line contains an integer ~n~ (~1 \le n \le 2 \cdot 10^5~) — the number of gem levels.

The second line contains ~n~ integers ~a_1, a_2, \ldots, a_n~ (~0 \le a_i \le 10^9~) — the number of gems you have at each level.

The third line contains ~n~ integers ~b_1, b_2, \ldots, b_n~ (~0 \le b_i \le 10^9~) — the number of gems required at each level.

The sum of ~n~ in all test cases is guaranteed not to exceed ~2 \cdot 10^5~.

Output

For each test case, print "YES" if there is a way to exchange gems to have enough gems at each level, or "NO" otherwise.

Scoring

Sample Input 1

4
4
1 1 4 5
3 1 2 3
2
1 0
0 1
3
1 1 1
1 1 1
1
1
100

Sample Output 1

YES
NO
YES
NO

Notes

In the first test case, you can:

• Exchange ~1~ gem at level ~2~ for ~2~ gems at level ~1~. The number of gems you have at each level becomes ~[3, 0, 4, 5]~.

• Exchange ~1~ gem at level ~3~ for ~2~ gems at level ~2~. The number of gems you have at each level becomes ~[3, 2, 3, 5]~.

Now, you have enough gems at each level.

In the second test case, you only have ~1~ gem at level ~1~, so you cannot perform any gem exchange. Therefore, you cannot have enough gems at level ~2~ as required.

In the third test case, you already have enough gems at each level from the beginning.

In the fourth test case, the system has only ~1~ gem level, so you cannot perform any gem exchange, and you also do not have enough gems at level ~1~ as required.

Given a non-negative integer ~x~, please find a sequence of integers ~a_1, a_2, \ldots, a_n~ such that:

• ~0 \le a_i \le x~ for all ~1 \le i \le n~.

• AND-sum of every contiguous subsequence of ~a~ is pairwise different.

  Formally, denote ~f(l, r)=a_l \,\&\, a_{l+1} \,\&\, \ldots \,\&\, a_r~ (AND-sum of contiguous subsequence from position ~l~ to position ~r~). For all possible 4-tuple ~(l_1, r_1, l_2, r_2)~ such that ~l_1 \le r_1~, ~l_2 \le r_2~ and ~(l_1, r_1) \ne (l_2, r_2)~, we have ~f(l_1, r_1) \ne f(l_2, r_2)~.

• The length ~n~ is maximized.

Input

The input consists of multiple test cases. The first line of the input contains a positive integer ~t~ (~1 \le t \le 10~) which is the number of test cases. The description of each test case is as follows.

Each test case consists of only integer ~x~ (~1 \le x \le 10^6~) — the upper bound of sequence ~a~ values.

Output

For each test case, print the answer in the following format:

The first line consists of an integer ~n~ (~1 \le n \le 2000~) — the length of sequence ~a~.

The second line consists of ~n~ integer ~a_1, a_2, \ldots, a_n~ (~0 \le a_i \le x~) — the elements of ~a~.

It can be shown that the length of sequence ~a~ that satisfies the problem's conditions can not exceed ~2000~.

Scoring

Sample Input 1

2
1
2

Sample Output 1

1
1
2
1 2

Notes

In the second test case, with ~a = [1, 2]~, we have:

• The subarray ~[1]~ has an AND-sum value of ~1~.

• The subarray ~[2]~ has an AND-sum value of ~2~.

• The subarray ~[1, 2]~ has an AND-sum value of ~1 \,\&\, 2 = 0~.

All three subarrays have distinct AND-sum values, so the sequence ~a~ satisfies the requirements of the problem. It can be proven that there does not exist a sequence ~a~ with a length of ~3~ or more that satisfies the requirements of the problem.

Given ~n~ magnets on the ~Ox~ coordinate axis, the ~i~-th magnet has coordinate ~x_i~. The magnets are numbered from ~1~ to ~n~ in increasing order of coordinates and have negligible size. You can perform the following operation any number of times:

• Choose two magnets ~i~ and ~j~ (~i < j~) and a real number ~t~.

• Activate magnets ~i~ and ~j~ with parameter ~t~. Then, magnet ~i~ will move to coordinate ~x_i + t~, and magnet ~j~ will move to coordinate ~x_j - t~.

• The magnets are not allowed to pass each other during the movement. In other words, ~t \le \min\left(\frac{x_j - x_i}{2}, x_{i+1} - x_i, x_j - x_{j-1}\right)~.

• You will receive a score of ~t~.

Find the maximum total score that can be obtained after performing the operations.

Input

The input consists of multiple test cases. The first line of the input contains a positive integer ~t~ (~1 \le t \le 100~) which is the number of test cases. The description of each test case is as follows.

The first line contains an integer ~n~ (~2 \le n \le 2 \cdot 10^5~) — the number of magnets.

The second line contains ~n~ integers ~x_1, x_2, \ldots, x_n~ (~0 \le x_1 < x_2 < \ldots < x_n \le 10^6~) — the coordinates of the magnets.

The sum of ~n~ in all test cases is guaranteed not to exceed ~2 \cdot 10^5~.

Output

For each test case, output a single real number which is the maximum total score that can be obtained.

Let ~J~ be the answer from the judges, and ~P~ be the output you provide. Your output will be considered correct if the relative or absolute error compared to the judges' answer does not exceed ~10^{-6}~, i.e., ~\displaystyle\frac{|P - J|}{\max\{1, |J|\}} \le 10^{-6}~.

Scoring

Sample Input 1

2
2
1 4
3
0 1 2

Sample Output 1

1.5
2

Notes

In the first example, we will choose two magnets at coordinates ~1~ and ~4~ with ~t = 1.5~. The coordinates after performing the operation are ~[2.5, 2.5]~. We cannot perform any other operations, so the maximum total score is ~1.5~.

In the second example, we will perform the operations as follows:

• Choose two magnets at coordinates ~0~ and ~1~ and ~t = 0.5~. The coordinates after performing the operation are ~[0.5, 0.5, 2]~

• Choose two magnets at coordinates ~0.5~ and ~2~ with ~t = 0.5~. The coordinates after performing the operation are ~[0.5, 1, 1.5]~

• Choose two magnets at coordinates ~0.5~ and ~1~ with ~t = 0.25~. The coordinates after performing the operation are ~[0.75, 0.75, 1.5]~

• Choose two magnets at coordinates ~0.75~ and ~1.5~ with ~t = 0.25~. The coordinates after performing the operation are ~[0.75, 1, 1.25]~

• ...

The total score is ~0.5 + 0.5 + 0.25 + 0.25 + ... = 2 \times \sum_{x=1}^{\infty} \left( \frac{1}{2} \right)^x = 2~.

In the 2D coordinate system, we draw ~n~ zigzag lines, with the ~i~-th zigzag line starting from the point ~(x_i, y_i)~, having a length of ~l_i~, and belonging to one of two types:

• Type ~0~: Starting from ~(x_i, y_i)~, we connect the points ~(x_i, y_i) \to (x_i + 1, y_i) \to (x_i + 1, y_i + 1) \to (x_i + 2, y_i + 1) \to (x_i + 2, y_i + 2) \to \dots \to (x_i+\left\lceil\frac{l_i}{2}\right\rceil, y_i+\left\lfloor\frac{l_i}{2}\right\rfloor)~.

• Type ~1~: Starting from ~(x_i, y_i)~, we connect the points ~(x_i, y_i) \to (x_i, y_i + 1) \to (x_i + 1, y_i + 1) \to (x_i + 1, y_i + 2) \to (x_i + 2, y_i + 2) \to \dots \to \left(x_i+\left\lfloor\frac{l_i}{2}\right\rfloor, y_i+\left\lceil\frac{l_i}{2}\right\rceil\right)~.

The function ~f(i, j)~ is the number of common integer points between the ~i~-th and ~j~-th zigzag lines. Calculate ~\sum_{i = 1}^n \sum_{j=i+1}^n f(i, j)~.

Input

The input consists of multiple test cases. The first line of the input contains a positive integer ~t~ (~1 \le t \le 10\,000~) representing the number of test cases. The description of each test case is as follows.

The first line contains an integer ~n~ (~1 \le n \le 2 \cdot 10^5~) — the number of zigzag lines.

The ~i~-th line among the next ~n~ lines contains four integers ~x_{i}, y_{i}, l_i, c_i~ (~0 \le x_i, y_i \le 10^6~, ~2 \le l_i \le 10^6~, ~0 \le c_i \le 1~) — the ~i~-th zigzag line starts from point ~(x_i, y_i)~, with length ~l_i~, and belongs to type ~c_i~.

The sum of ~n~ in all test cases is guaranteed not to exceed ~2 \cdot 10^5~.

Output

For each test case, output the answer to the problem.

Scoring

For each test case, define ~X = \max(\max x, \max y, \max l)~.

Sample Input 1

2
2
0 0 3 0
0 1 3 0
3
2 3 5 0
2 3 8 1
3 3 3 0

Sample Output 1

1
5

Sample Input 2

2
5
10 10 2 0
9 9 10 1
0 0 20 0
0 0 30 0
1 1 40 0
3
15 20 12 0
20 15 34 0
10 10 56 1

Sample Output 2

92
0

Notes

Below is an illustration for the first test case of the first example.

The red line and the blue line are the first and second zigzag lines in the input, respectively. They intersect at the dotted point shown in the illustration.

Below is an illustration for the second test case of the first example.

The red, navy blue, and green lines are the first, second, and third zigzag lines in the input, respectively. The navy blue line and the red line have ~3~ common integer points, while the red line and the green line have ~2~ common integer points.

You are given an integer ~k~ and a string ~s~ of length ~n~. Imagine writing out all ~2^n - 1~ non-empty subsequences~^\dagger~ of ~s~. Count the number of different strings ~t~ that were written down exactly ~k~ times. Because the answer can be huge, you need to output it modulo ~998\,244\,353~.

~^\dagger~ A string ~t~ is a subsequence of ~s~ if there is a way to erase some (possibly zero) characters from ~s~ to obtain ~t~.

Input

Each test contains multiple test cases. The first line contains the number of test cases ~t~ (~1 \leq t \leq 10\,000~), followed by ~k~ (~1 \leq k \leq 2~), the intended number of occurrences, which is the same for every test case. The description of each test case is as follows.

The first line of each test case contains ~n~ (~1 \le n \le 3 \cdot 10^5~) describing the length of string ~s~.

The second line of each test case contains the string ~s~ consisting of ~n~ lowercase Latin characters.

The sum of ~n~ in all test cases is guaranteed not to exceed ~3 \cdot 10^5~.

Output

For each test case, print one integer — the number of strings that have exactly ~k~ occurrences as a subsequence in ~s~, modulo ~998\,244\,353~.

Scoring

Sample Input 1

3 2
3
aab
10
vnoihaibon
35
hiiamcurrentlyafirstyearphdstudents

Sample Output 1

2
74
911464594

Sample Input 2

3 1
3
aab
7
vnoicup
38
asomewhatnotshortblogonflowwithdemands

Sample Output 2

3
127
395878133

Notes

The first test case of both examples has ~s = \mathtt{aab}~. All non-empty subsequences of ~s~ are ~[\mathtt{a}, \mathtt{a}, \mathtt{b}, \mathtt{aa}, \mathtt{ab}, \mathtt{ab}, \mathtt{aab}]~. Among these, ~\mathtt{b}~, ~\mathtt{aa}~, and ~\mathtt{aab}~ appears once, while ~\mathtt{a}~ and ~\mathtt{ab}~ appears twice.

Given a multiset ~S~ of ~n~ non-negative integers. Perform ~q~ queries of one of the following three types:

• ~\mathtt{1\;} x~: Add ~x~ to ~S~.

• ~\mathtt{2\;} x~: Remove one occurrence of ~x~ from ~S~.

• ~\mathtt{3\;} k~: Among all ways to partition ~S~ into ~k~ non-empty sub-multisets ~S_1,S_2,\ldots, S_k~, find the partition with the maximum sum ~\displaystyle \sum_{i=1}^k \operatorname{cost}(S_i)~. Here, for ~X=\{x_1, x_2, \ldots, x_q\}~, define ~\operatorname{cost}(X)=x_1\,\&\,x_2\,\&\,\ldots\,\&\,x_q~ where ~\&~ is the bitwise AND operation.

Input

The first line contains two integers ~n~ and ~q~ (~1\le n, q\le 10^5~) — the number of elements in ~S~ and the number of queries.

The second line contains ~n~ non-negative integers ~s_1,s_2,\ldots,s_n~ (~0\le s_i<2^{30}~) — the elements of ~S~.

Each of the next ~q~ lines contains two integers describing the queries. The first integer ~t~ takes a value from ~\{1,2,3\}~.

• If ~t=1~, the next integer is ~x~ (~0\le x<2^{30}~) — the integer to be added to ~S~.

• If ~t=2~, the next integer is ~x~ (~0\le x<2^{30}~; ~x \in S~) — the integer to be removed from ~S~.

• If ~t=3~, the next integer is ~k~ (~1\le k\le |S|~) — the number of sub-multisets to partition into.

Output

For each type ~3~ query, output an integer which is the result of the query on a new line.

Scoring

Sample Input 1

3 5
3 4 5
3 2
1 4
3 3
2 5
3 2

Sample Output 1

7
12
7

Sample Input 2

6 6
5 5 6 6 7 7
3 1
3 2
3 3
3 4
3 5
3 6

Sample Output 2

4
11
18
25
31
36

Notes

For the first example, the initial multiset is ~\{3, 4, 5\}~:

1. One optimal partition for ~k=2~ is ~\{3\}, \{4, 5\}~.

2. The new multiset after adding ~4~ is ~\{3, 4, 4, 5\}~.

3. One optimal partition for ~k=3~ is ~\{3\}, \{4, 4\}, \{5\}~.

4. The new multiset after removing ~5~ is ~\{3, 4, 4\}~.

5. One optimal partition for ~k=2~ is ~\{3\}, \{4, 4\}~.