Humanity is in danger because of monsters coming from space. In this precarious situation, a superhero has appeared to rescue humanity from ~n~ monsters.

Initially, the superhero has a power level of ~x~. At step ~i~, the superhero can:

• Choose an undefeated monster whose health level does not exceed the superhero's power level.

• If such a monster can be chosen, it will be defeated, and the superhero's power level will be multiplied by ~i + 1~; otherwise, the superhero's power level remains the same.

• The health level of all undefeated monsters is multiplied by ~i~, regardless of whether the superhero has just defeated a monster.

Calculate the maximum amount of monsters the hero can defeat.

Input

Each test consists of multiple test cases. The first line contains the number of test cases ~t~ (~1 \leq t \leq 100~). The description of each test case is as follows.

The first line contains two positive integers ~n~ and ~x~ (~1 \le n \le 5000~, ~1 \le x \le 10^{12}~) — the number of monsters and the initial power level of the superhero.

The second line contains ~n~ positive integers ~a_1, a_2, ..., a_n~ (~1 \le a_i \le 10^{12}~) — the initial health levels of the monsters.

The sum of ~n~ across all test cases is guaranteed not to exceed ~5000~.

Output

For each test case, output a single integer — the maximum number of monsters the superhero can defeat.

Scoring

Sample Input 1

2
5 3
1 1 1 1 50
3 2
7 1 1

Sample Output 1

4
2

Notes

The following explains the first test case, with ~-~ representing monsters that have been defeated.

• The hero chooses the first monster. After the superhero defeats the first monster, the remaining monsters have health levels of ~[-, 1, 1, 1, 50]~. The superhero's power level is ~6~.

• The hero chooses the second monster. After the superhero defeats the second monster, the remaining monsters have health levels of ~[-, -, 2, 2, 100]~. The superhero's power level is ~18~.

• The hero chooses the third monster. After the superhero defeats the third monster, the remaining monsters have health levels of ~[-, -, -, 6, 300]~. The superhero's power level is ~72~.

• The hero chooses the fourth monster. After the superhero defeats the fourth monster, the remaining monsters have health levels of ~[-, -, -, -, 1200]~. The superhero's power level is ~360~.

• No more monsters can be defeated.

There are ~n~ marble slots evenly distributed on a circular path. The slots are numbered from ~1~ to ~n~ in the clockwise direction. Additionally, there is a marble holder located at the center of the circular path, numbered ~n+1~.

Initially, with ~n~ marble slots on the circular path, slot ~i~ contains exactly one marble with color ~a_i~, and slot ~n+1~ is empty. The marbles are colored from ~1~ to ~n~, and no two marbles have the same color. You can move a marble from a slot containing a marble to an empty slot if the two slots are adjacent on the circular path, or if one of the slots is slot ~n+1~.

Find a sequence of marble moving operations to rearrange the marbles so that the marble with color ~i~ is in slot ~i~, while the number of operations does not exceed ~1500~.

Input

Each test consists of multiple test cases. The first line contains the number of test cases ~t~ (~1 \leq t \leq 50~). The description of each test case is as follows.

The first line contains an integer ~n~ (~3 \le n \le 50~) – the number of marble slots on the circular path.

The second line consists of ~n~ integers ~a_1, a_2, \ldots, a_n~ (~1 \le a_i \le n~) – the colors of the marbles in the ~n~ marble slots on the circular path. Each marble color will appear exactly once.

Output

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

On the first line, output an integer ~k~ (~0 \le k \le 1500~) – the number of marble moving operations to be performed.

On the ~i~-th line in the next ~k~ lines, output two integers ~s_i~ and ~t_i~ (~1 \le s_i, t_i \le n+1~, ~s_i \ne t_i~) describing the moving operation of the ~i~-th marble (from slot ~s_i~ to slot ~t_i~). Slot ~s_i~ must contain a marble, and slot ~t_i~ must be empty.

It can be proven that there always exists a way to rearrange the marbles satisfying the requirements of the problem statement.

Scoring

Sample Input 1

2
3
2 3 1
3
1 2 3

Sample Output 1

4
3 4
2 3
1 2
4 1
0

Notes

For the first test case, the diagram below illustrates a way to rearrange the marbles satisfying the requirements of the problem statement. The numbers outside the marble slots indicate the slot numbers, and the numbers inside indicate the color of the marble in the slot.

For the second test case, all marbles are already in their correct slots, so no marble moving operations are needed.

After realizing that the previous problem was too difficult for the position as the third problem of the second round of VNOI CUP, the problem setters quickly came up with the following problem.

• Given two arrays of integers ~a~ and ~c~, both of length ~n~, find the minimum value of the following expression, where ~x~ is an arbitrary integer:

  $$\sum_{i=1}^n c_i \cdot |a_i - x|$$

However, the problem setters still don't know how to solve this problem. Can you help them?

Input

Each test consists of multiple test cases. The first line contains the number of test cases ~t~ (~1 \leq t \leq 10\,000~). The description of each test case is as follows.

The first line contains an integer ~n~ (~1 \le n \le 3 \cdot 10^5~) — the length of arrays ~a~ and ~c~.

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

The third line contains ~n~ integers ~c_1, c_2, \ldots, c_n~ (~-10^6 \le c_i \le 10^6~) — the elements of array ~c~.

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

Output

For each test case, if the value of the expression can go down to negative infinity, output ~\texttt{-inf}~. Otherwise, output the integer which is the minimum value of the expression.

Scoring

Sample Input 1

4
6
1 2 3 4 5 6
1 1 1 1 1 1
6
-4 -2 0 2 4 6
-1 -1 -1 -1 -1 -1
3
-100 0 100
1 0 -1
10
2 -8 4 -8 7 8 -1 -5 -7 -6
2 0 10 10 9 -4 -10 9 2 7

Sample Output 1

9
-inf
-200
158

Notes

In the first test case, with ~x = 3~, the value of the expression is ~9~. We can prove that there is no value of ~x~ that can make the expression smaller than ~9~.

In the second test case, as ~x~ approaches ~\infty~, the value of the expression approaches ~-\infty~.

Having lived nearly twenty years without a lover, Trung decided to go to the temple to seek love. After completing all the rituals, Trung received a love charm. The charm contains a string of length ~n~ consisting of only two letters ~\texttt{O}~ or ~\texttt{K}~. With deep understanding of his own destiny, Trung knows that the effectiveness of the charm depends on the consecutive pairs of letters. Specifically:

• The pair ~\texttt{OK}~ has an effect, so if the charm has ~a~ pairs of ~\texttt{OK}~, the effectiveness of the charm will increase by ~a^2~.

• The pair ~\texttt{KO}~ has a counter-effect, so if the charm has ~b~ pairs of ~\texttt{KO}~, the effectiveness of the charm will decrease by ~b^2~.

In other words, if the charm has ~a~ pairs of ~\texttt{OK}~ and ~b~ pairs of ~\texttt{KO}~, the effectiveness of the charm will be ~a^2 - b^2~. For example, if the charm contains the string ~\texttt{OOOKOO}~, then ~a = 1~, ~b = 1~, so the effectiveness of the charm will be ~1^2 - 1^2 = 0~.

Trung is not very satisfied with his charm, so he asked the temple for another charm. However, the temple only allows Trung to change the current charm up to ~k~ times, each time Trung can choose any two letters on the charm and swap them. Help Trung obtain a love charm with the maximum possible effectiveness!

Input

Each test contains multiple test cases. The first line contains the number of test cases ~t~ (~1 \leq t \leq 10\,000~). The description of each test case is as follows.

The first line contains two positive integers ~n~ and ~k~ (~2 \leq n \leq 10^5~, ~1 \leq k \leq 10~) — the length of the string written on the charm and the maximum number of transformations.

The second line contains a string ~s~ consisting of ~n~ characters ~\texttt{O}~ or ~\texttt{K}~, describing the string written on the charm.

The sum of ~n~ over all test cases is guaranteed not to exceed ~10^5~.

Output

For each test case, output an integer which is the maximum effectiveness the charm can achieve.

Scoring

Sample Input 1

5
2 1
KO
2 1
OK
7 1
OOOKKKK
7 1
KKOOKKK
10 2
KOOKOKKKOO

Sample Output 1

1
1
5
3
9

Notes

In the first test case, the optimal swapping sequence is ~\mathtt{KO}~ ~\to \mathtt{OK}~. The resulting charm has an effectiveness of ~1~.

In the second test case, it is optimal to keep the string as ~\mathtt{OK}~, with an effectiveness of ~1~.

In the fifth test case, an optimal swapping sequence is ~\mathtt{KO}~~\mathtt{OKOKKKOO} \to \mathtt{OKOKOK}~~\texttt{K}~~\texttt{KO}~~\texttt{O}~ ~\to \mathtt{OKOKOKOKOK}~, resulting in a charm with an effectiveness of ~9~.

A company has ~n~ offices labeled from ~1~ to ~n~. This company is creating an interconnected network between the offices (one may call it the company's inter-net) by setting up several two-way connections between offices, such that any distinct offices ~i~ and ~j~ (~i \neq j~) can connect to each other via these connection.

There are ~k~ inter-net providers supplying a total of ~m~ possible connections, the ~i~-th of which connects office ~u_i~ with office ~v_i~, is operated by the ~c_i~-th provider, and costs ~p_i~ dong~^\dagger~ to set up (note that there may be several connections between any two offices).

Furthermore, to boost competition, all ~k~ providers are offering customer loyalty program; specifically, if the company pays the ~j~-th provider an amount more than ~s_j~, the ~j~-th provider will apply a ~50\%~-off discount for the extra amount. Formally, this means that the provider will charge ~x_j - \frac{\max(0, x_j - s_j)}{2}~, where ~x_j~ is the total cost incurred to this provider.

Find the cheapest way to connect all the offices. Since this number times ~2~ can be proven to be an integer, please output the cheapest cost multiplied by ~2~.

~^\dagger~ ~1~ million dong equals approximately ~420~ Norwegian Kroner.

Input

Each test consists of multiple test cases. The first line contains the number of test cases ~t~ (~1 \leq t \leq 100~). The description of each test case is as follows.

The first line contains three integers ~n~, ~m~, and ~k~ (~2 \leq n \leq 1000~, ~n - 1 \leq m \leq 5 \cdot 10^5~, ~1 \leq k \leq 10~) —the number of offices, the number of possible connections, and the number of inter-net providers.

The ~i~-th line of the next ~m~ lines contains four integers ~u_i~, ~v_i~, ~c_i~, ~p_i~ (~1 \leq u_i, v_i \leq n~, ~u_i \neq v_i~, ~1 \leq c_i \leq k~, ~1 \leq p_i \leq 10^9~) describing the ~i~-th connection.

The last line contains ~k~ integers ~s_1, s_2, \cdots, s_k~ (~1 \leq s_i \leq 10^9~) describing the customer loyalty program of the ~k~ providers.

For each test case, it is guaranteed that there is at least one way to set up the connections such that all ~n~ offices are (directly or indirectly) connected.

The sum of ~n~ across all test cases is guaranteed not to exceed ~1000~, and the sum of ~m~ is guaranteed not to exceed ~5 \cdot 10^5~.

Output

For each test case, output one integer —the minimum cost (in dong) for setting up an interconnected network multiplied by ~2~.

Scoring

Sample Input 1

4
3 4 2
1 2 1 3
2 3 1 5
1 2 2 4
1 3 2 4
5 6
3 4 2
1 2 1 3
2 3 1 5
1 2 2 4
1 3 2 4
1 1
5 7 3
1 5 3 100
1 2 1 5
4 5 1 5
1 3 2 7
2 3 3 10
1 2 2 4
4 5 2 4
5 20 100
2 3 3
1 2 1 5
1 2 2 6
1 2 3 7
6 2 2

Sample Output 1

13
9
225
8

Notes

For the first test case, the illustration below represents the allowed connections for installation, with the red connections belonging to provider ~1~ and the blue connections belonging to provider ~2~. For ~s = [5, 6]~, we should install the highlighted connections. The total cost pre-discount to be paid for provider ~1~ and provider ~2~ respectively is ~[8, 0]~, so the total cost post-discount is ~\left(8 - \frac{\max(0, 8 - 5)}{2}\right) + \left(0 - \frac{\max(0, 0 - 6)}{2}\right) = \frac{13}{2}~.

For the second test case, the allowed connections for installation are similar to the first test case. For ~s = [1, 1]~, we should install the highlighted connections. The total cost pre-discount to be paid for provider ~1~ and provider ~2~ respectively is ~[3, 4]~, so the total cost post-discount is ~\left(3 - \frac{\max(0, 3 - 1)}{2}\right) + \left(4 - \frac{\max(0, 4 - 1)}{2}\right) = \frac{9}{2}~.

Given a directed graph ~G~ consisting of ~n~ vertices and ~m~ edges, where the ~i~-th edge connects vertex ~u_i~ to vertex ~v_i~. Additionally, you are given a walk ~P~ from vertex ~1~ to vertex ~n~ ~^\dagger~, using edges ~p_1, p_2, \ldots, p_k~ in that order.

You need to find the minimum number of edges that need to be removed from ~G~ for ~P~ to become the unique walk from vertex ~1~ to vertex ~n~. If there is no way to remove edges to satisfy the condition, print ~-1~.

~^\dagger~ A walk ~P~ from vertex ~1~ to vertex ~n~ is an ordered list of edge indices ~p_1, p_2, \dots, p_k~ such that:

• ~u_{p_1} = 1~.

• ~v_{p_i} = u_{p_{i + 1}}~ for every ~1 \le i < k~.

• ~v_{p_k} = n~.

Input

Each test consists of multiple test cases. The first line contains the number of test cases ~t~ (~1 \leq t \leq 10\,000~). The description of each test case is as follows.

The first line contains three integers ~n~, ~m~, and ~k~ (~2 \le n \le 10^5~, ~1 \le m, k \le 10^5~) — the number of vertices and edges in the graph ~G~, and the number of edges in the walk ~P~.

The ~i~-th line among ~m~ next lines contains two integers ~u_i~ and ~v_i~ (~1 \le u_i, v_i \le n~, ~u_i \neq v_i~) — the ~i~-th edge of the graph ~G~.

The next line contains ~k~ integers ~p_1, p_2, \ldots, p_k~ (~1 \le p_i \le m~) representing a walk from ~1~ to ~n~. It is guaranteed that these edge indices form a walk from ~1~ to ~n~.

The sum of ~n~, the sum of ~m~, and the sum of ~k~ over all test cases are guaranteed not to exceed ~10^5~.

Output

For each test case, output an integer — the minimum number of edges that need to be removed for ~P~ to become the unique walk from vertex ~1~ to vertex ~n~. If there is no way to remove edges to satisfy the condition, print ~-1~.

Scoring

~^\ddagger~ A directed graph is weakly connected if replacing all of its directed edges with undirected edges produces a connected (undirected) graph.

Sample Input 1

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

Sample Output 1

1
2
-1

Notes

For the first test case, the following diagram shows the graph ~G~, with the walk ~P~ highlighted in red. We need to remove the third edge (corresponding to ~4 \to 3~), as there is the walk ~1 \to 3 \to 2 \to 4 \to 3 \to 2 \to 4 \to 5~ that uses this edge and goes from ~1~ to ~5~.

For the second test case, the following diagram shows the graph ~G~, with the walk ~P~ highlighted in red. We need to remove the ~2 \to 3~ and the ~3 \to 1~ edges.

You are given a positive even integer ~n~, and ~k~ pairs of numbers ~(l_i, r_i)~ satisfying the condition ~1 \le l_1 < r_1 < l_2 < r_2 < \ldots < l_k < r_k \le n~. Count the number of valid bracket sequences~^\dagger~ ~s~ of length ~n~ satisfying the following condition, modulo ~998\,244\,353~:

• For every ~1 \le i \le k~, ~s_{l_i} \neq s_{r_i}~.

~^\dagger~ A string ~s~ formed from two types of characters ~\mathtt{(}~ and ~\mathtt{)}~ is called a valid bracket sequence if ~s~ satisfies one of the following conditions:

• ~s~ is empty.

• ~s~ has the form "~\mathtt{(} t \mathtt{)}~", where ~t~ is also a bracket sequence.

• ~s~ has the form "~ab~", where ~a~ and ~b~ are two valid bracket sequences.

Input

Each test contains multiple test cases. The first line contains the number of test cases ~t~ (~1 \leq t \leq 10\,000~). The description of each test case is as follows.

The first line contains two integers ~n~ and ~k~ (~2 \le n \le 2 \cdot 10^5~, ~n~ is even, ~0 \le k \le \frac{n}{2}~) — the length of string ~s~ and the number of given pairs.

The ~i~-th line in the next ~k~ lines contains two integers ~l_i~ and ~r_i~ representing the ~i~-th given pair. It is guaranteed that the condition ~1 \le l_1 < r_1 < l_2 < r_2 < \ldots < l_k < r_k \le n~ holds.

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

Output

For each test case, output an integer which is the number of valid strings ~s~ satisfying the given condition, modulo ~998\,244\,353~.

Scoring

Sample Input 1

5
6 0
4 2
1 2
3 4
8 1
1 8
8 2
1 3
5 8
20 4
2 8
9 10
15 17
19 20

Sample Output 1

5
1
14
3
692

Notes

In the first test case, valid bracket sequences are ~\mathtt{((()))}~, ~\mathtt{(()())}~, ~\mathtt{(())()}~, ~\mathtt{()(())}~, ~\mathtt{()()()}~.

In the second test case, the only valid bracket sequence is ~\mathtt{()()}~.

In the fourth test case, valid bracket sequences are ~\mathtt{(())(())}~, ~\mathtt{(())()()}~, ~\mathtt{(()(()))}~.