Tishreen + SVU CPC 2023
A. CBS Bracket Sequence
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

After Da7doo7 got fired from his previous job, he Started a business of fixing bracket sequences and he needs your help.

You are given a bracket sequence$$$^\dagger$$$ and you want to apply some operations (possibly zero) to make it a regular bracket sequence$$$^\ddagger$$$.

In each operation, two brackets will be appended to the sequence, one of them at the beginning and the other at the end of the sequence, you can choose the state of each bracket as you wish.

In other words, let the current sequence be $$$s$$$. After applying one operation $$$s$$$ will become one of these sequences:

  • $$$s \; \gets \; \texttt{(} s \texttt{(}$$$
  • $$$s \; \gets \; \texttt{(} s \texttt{)}$$$
  • $$$s \; \gets \; \texttt{)} s \texttt{(}$$$
  • $$$s \; \gets \; \texttt{)} s \texttt{)}$$$

You are asked to find the minimum number of operations required to make $$$s$$$ a regular bracket sequence$$$^\ddagger$$$ or report that it is impossible.

$$$^\dagger$$$ A bracket sequence is a string containing only the characters "(" and ")".

$$$^\ddagger$$$ A regular bracket sequence is a bracket sequence that can be transformed into a valid math expression by inserting characters "1" and "+" between the original characters of the sequence. For example:

  • the bracket sequences "()()" and "(())" are regular becuase their resulting expressions are "(1)+(1)" and "((1+1)+1)" respectively.
  • the bracket sequences ")(", "(" and ")" are not.
Input

The first line contains a single integer $$$T$$$ $$$(1\le T\le 10^5)$$$ denoting the number of test cases.

Each of the following $$$T$$$ lines contains a bracket sequence $$$s$$$ $$$(1\le |s|\le 5\cdot 10^5)$$$.

It is guaranteed that the sum of $$$|s|$$$ over all test cases does not exceed $$$5\cdot 10^5$$$.

Output

For each test case, if there is no way to make $$$s$$$ regular, print $$$-1$$$. Otherwise, print the minimum number of operations required to make $$$s$$$ regular.

Example
Input
3
)(()
)((
(())
Output
1
-1
0

B. GCN
time limit per test
1 second
memory limit per test
128 megabytes
input
standard input
output
standard output

After Da7doo7 got fired again, he decided to count things for a living. Then, he struggled with this problem, so he called you for help.

You are given a tree consisting of $$$n$$$ nodes.

  • Let $$$\langle a, b \rangle$$$ be the set containing all nodes of the simple path between nodes $$$a$$$ and $$$b$$$, where $$$a \lt b$$$.
  • Let $$$GCN[\langle a, b \rangle, \langle c, d \rangle]$$$ be the number of nodes that are in both of the sets $$$\langle a, b \rangle$$$ and $$$\langle c, d \rangle$$$.

Your task is to find the sum of $$$GCN$$$ over all different unordered pairs of distinct sets in the given tree, modulo $$$10^9+7$$$.

Note
  • Do not count $$$GCN[\langle a, b \rangle, \langle a, b \rangle]$$$.
  • $$$GCN[\langle a, b \rangle, \langle c, d \rangle]$$$ and $$$GCN[\langle c, d \rangle, \langle a, b \rangle]$$$ are considered the same pair of sets, do not count them twice.
Input

The first line of the input contains an integer $$$T$$$ $$$(1\le T\le 10^5)$$$ denoting the number of test cases.

The first line of each test case contains an integer $$$n$$$ $$$(2\le n \le 5\cdot 10^5)$$$ — the number of nodes in the tree.

The second line of each test case contains $$$n-1$$$ integers $$$p_2, \ldots, p_n$$$ $$$(1\le p_i \le n)$$$ — indicating that there is an edge between nodes $$$i$$$ and $$$p_i$$$.

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

Output

For each test case, print the answer in a single line.

Example
Input
2
4
1 2 3
4
1 1 1
Output
26
24

C. United We Stand Divided We Fall
time limit per test
6 s
memory limit per test
256 MB
input
standard input
output
standard output
                  "Teamwork is everything                           Take the ball                           Pass the ball"
— Pep Algorithmola

The great football coach Pep Algorithmola hired Da7doo7(after he got fired again) to solve this problem for him because unlike football he is bad at math and so is Da7doo7 so he asked you to solve it.

He has a team of $$$n$$$ members numbered from $$$1$$$ to $$$n$$$. They are standing in a circle in the order of their numbers and pass the ball each to the next player the game starts from the smallest index ($$$1$$$ to $$$2$$$, $$$2$$$ to $$$3$$$, $$$\ldots$$$, $$$n-1$$$ to $$$n$$$, $$$n$$$ to $$$1$$$) and when a player gets tired from receiving balls he passes the ball one last time and leaves the circle. When only one person remains in the circle, he is announced as the winner and thus leaves the circle.

You know that each team member has strength $$$S_i$$$ which denotes that the $$$i$$$-th person passes the ball with strength $$$S_i$$$, and health $$$H_i$$$ which means that this person leaves the circle when the sum of strengths of all the passes he received is greater than or equal to $$$H_i$$$.

The coach wants to know the order in which his players will leave the circle. Can you help him find it?

Input

The first line contains a single integer $$$T$$$ ($$$1 \le T \le 10^5$$$) denoting the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 10^6$$$) denoting the number of players.

The second line of each test case contains $$$n$$$ positive integers $$$H_1, H_2, \ldots, H_n$$$ ($$$1 \le H_i \le 10^9$$$) indicating the health of each player.

The third line of each test case contains $$$n$$$ positive integers $$$S_1, S_2, \ldots, S_n$$$ ($$$1 \le S_i \le 10^9$$$) indicating the strength of each player.

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

Output

For each test case, output in a separate line the order in which the players will leave the circle.

Example
Input
2
5
4 5 6 2 1
2 2 2 1 4
2
1 1
1 1
Output
4 5 1 2 3 
2 1

D. Similarity
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

After Da7doo7 got fired he wanted to get an interview for another job so he hacked the PC of an HR to make his CV similar to the CVs of the employees. He needed your help and he gave you the information more formally.

Given $$$n$$$ strings of length $$$m$$$, you have to construct a string of length $$$m$$$ with maximum total similarity.

We define the similarity of two strings $$$a,b$$$ to be the number of indices $$$i$$$ $$$(1\le i\le m)$$$ where $$$a_i=b_i$$$.

The total similarity is equal to the sum of similarities of the string you constructed with all $$$n$$$ strings you are given.

We are not interested in the string itself, we only want the total similarity to be maximum possible.

Please print the maximum possible total similarity.

Input

The first line contains an integer $$$T$$$ $$$(1\le T\le 50)$$$ representing the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ $$$(1\le n,m\le 50)$$$ — the number of strings and their length.

The $$$i$$$-th of the following $$$n$$$ lines of each test case contain a string $$$s_i$$$ of length $$$m$$$.

Output

For each test case, print the maximum possible total similarity in a single line.

Example
Input
2
3 3
abc
ebd
fbd
2 3
abc
aff
Output
6
4
Note

In the first test case for example:

One of the possible strings with the maximum similarity is $$$ebd$$$,

The similarity of $$$s_1$$$ and $$$ebd$$$ is equal to $$$1$$$.

The similarity of $$$s_2$$$ and $$$ebd$$$ is equal to $$$3$$$.

The similarity of $$$s_3$$$ and $$$ebd$$$ is equal to $$$2$$$.

To the total similarity is: $$$1+3+2=6$$$

E. Interesting Ratios
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

After Da7doo7 got fired from his previous job, he became an online gamer. The internet was too slow, so he created this problem for fun:

You are monitoring the progress of a game download, and what interests you is the ratio of the completion percentage to the remaining percentage. It becomes particularly interesting when the ratio results in an integer value.

To put it simply, if the download progress reaches $$$75\%$$$, the ratio would be $$$75$$$ to $$$25$$$, which simplifies to $$$3$$$. Therefore, it is an interesting ratio.

Now, you have started another download, but it is not necessary to be out of $$$100$$$. In fact, it will be out of $$$n$$$. Your task is to calculate the sum of all interesting ratios that occur during the download process.

There will be $$$T$$$ downloads, you have to answer each one of them.

Input

The first line contains a single integer $$$T$$$ $$$(1\le T\le 10^5)$$$ denoting the number of downloads.

Each of the following $$$T$$$ lines contains a single integer $$$n$$$ $$$(1\le n\le 10^6)$$$.

Output

For each test case, print a single integer indicating the sum of all interesting ratios that occur during the $$$i$$$-th download process.

Example
Input
2
5
8
Output
4
11

F. Temporary Array
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Da7doo7 is facing this problem in a job interview and needs your help.

You are given an array $$$a$$$ of $$$n$$$ positive integers.

Every second, each of its border elements$$$^\dagger$$$ will decrease exactly by $$$1$$$. If at any moment some elements become zero, they will disappear from the array. For example:

$$$[\underline{1}, 3, \underline{2}] \;\; \xrightarrow[]{\texttt{one second}} \;\; [\underline{3}, \underline{1}] \;\; \xrightarrow[]{\texttt{one second}} \;\; [\underline{2}] \;\; \xrightarrow[]{\texttt{one second}} \;\; [\underline{1}] \;\; \xrightarrow[]{\texttt{one second}} \;\; []$$$

You have to answer $$$q$$$ independent queries. In each query, you are given a number $$$s$$$ and you have to determine how many elements will remain after $$$s$$$ seconds.

$$$^\dagger$$$ An element of an array is considered a border element if and only if it is either the leftmost or rightmost element of the array.

Note

If there is only one element remaining, then each second it will decrease by $$$1$$$, and not $$$2$$$.

Input

The first line of the input contains one integer $$$T$$$ $$$(1\le T\le 10^3)$$$ representing the number of test cases.

The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$q$$$ ($$$1\le n, q \le 2\cdot 10^5$$$) denoting the length of the array $$$a$$$ and the number of queries respectively.

The second line of each test case contains $$$n$$$ integers $$$a_1, \ldots, a_n$$$ ($$$1\le a_i\le 10^6$$$) — the elements of array $$$a$$$.

Each of the next $$$q$$$ lines of each test case contains a single integer $$$s$$$ ($$$0\le s\le 10^{12}$$$) — the query.

It is guaranteed that the sum of $$$n$$$ over all test cases, as well as the sum of $$$q$$$, does not exceed $$$2\cdot 10^5$$$.

Output

For each query, output how many elements will remain after $$$s$$$ seconds.

Example
Input
3
5 3
1 4 2 3 5
1
5
2
5 4
1 2 2 1 5
3
5
6
10
1 3
5
4
5
6
Output
4
2
4

3
1
0
0

1
0
0

G. Charging Power
time limit per test
6 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Being unemployed, Da7doo7 is sleeping in the middle of the day and has this dream:

Ali Zaiback is traveling between cities that form a tree structure, there are $$$n$$$ cities in total. Each city has an affection value, denoted by $$$a_i$$$. While traversing the tree, Ali can utilize his power card, which affects his power (which is initially equal to zero) by adding the affection value of the city he visits ($$$a_i$$$ can be negative, representing power drain).

Due to time constraints, Ali can visit at most $$$m$$$ different cities and use his power card no more than $$$k$$$ times. Ali cannot revisit any city, and he has the freedom to choose any city as his starting point.

You are required to determine the maximum power Ali can achieve during his journey.

Input

The first line contains a single integer $$$T$$$ $$$(1\le T\le 1000)$$$ denoting the number of test cases.

The first line of each test case contains three integers $$$n,m,k$$$ $$$(1\le k\le m\le n\le 3000)$$$ — the number of cities, the maximum number allowed for visiting different cities, and the maximum number allowed for utilizing the power card.

The second line contains an array of integers $$$a_i$$$ $$$(-10^6\le a_i\le 10^6)$$$ — the elements of the array $$$a$$$.

Each of the following $$$n-1$$$ lines of each test case contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n, u \neq v$$$) — the vertices connected by an edge. It is guaranteed that these edges form a tree.

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

Output

For each test case, print the maximum power Ali can achieve in a single line.

Example
Input
2
5 3 2
3 4 7 5 2
1 2
1 3
1 4
1 5
5 3 2
3 4 7 5 2
1 2
1 3
2 4
2 5
Output
12
11

H. X Y ?
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

After Getting fired again, Da7doo7 called FzArK who gave him a job as a mathematician. On his first day, FzArk gave him this problem and he forward it to you because Da7doo7 is bad at math.

You are given a tuple $$$\langle p, a, b, x, y \rangle$$$ of positive integers that satisfy the following:

  • $$$p$$$ is a prime number
  • $$$a$$$ and $$$b$$$ are relatively prime
  • $$$p \;\; \vert \;\; x^a - y^b$$$

You have to answer $$$Q$$$ queries. In each query, help $$$\texttt{F} z \texttt{ArK}$$$ find the $$$\textbf{smallest}$$$ positive integer $$$z$$$ such that: (in case it exists)

  • $$$p \;\; \vert \;\; z^a - y$$$
  • $$$p \;\; \vert \;\; z^b - x$$$
Note

Recall that for arbitrary positive integers $$$x$$$ and $$$y$$$, "$$$x \;\; \vert \;\; y$$$" $$$\textbf{is equivalent to}$$$ "$$$y$$$ is divisible by $$$x$$$".

Input

The first line contains a single integer $$$Q$$$ $$$(1 \le Q \le 10^5)$$$ denoting the number of queries.

The $$$i$$$-th of the next $$$Q$$$ lines contains five integers $$$p_i, a_i, b_i, x_i, y_i$$$ $$$(1 \le p_i, a_i, b_i, x_i, y_i \le 10^9 + 7)$$$.

It is guaranteed that $$$p_i$$$ is a prime number, $$$a_i$$$ and $$$b_i$$$ are relatively prime, and $$$p_i \;\; \vert \;\; x_i^{a_i} - y_i^{b_i}$$$.

Output

For each query, if no such $$$z$$$ exists, output $$$-1$$$. Otherwise, output the $$$\textbf{smallest}$$$ positive integer $$$z$$$ that satisfies both of the conditions.

Example
Input
3
2 2 1 4 6
7 10 3 13 2
67 3 2 1 1
Output
2
5
1

I. Link into the Vrains
time limit per test
2 seconds
memory limit per test
128 megabytes
input
standard input
output
standard output

Da7doo7 is watching TV after getting laid off today.

Yusaku and Ignister are dueling in a Yugi-oh game in Vrains (the virtual city), where Yusaku is fighting for people, whereas Ignister is fighting for the future of AI.

Yusaku has $$$n$$$ link monsters on the field, and each of them has a location $$$x_i$$$ and power $$$p_i$$$ (possibly negative).

It is a crucial game, and both Yusaku and Ignister are doing their best to win. Now, it is Yusaku's turn where he wants to inflict as much damage as possible to Ignister to win the duel, where the damage is equal to the sum of the power of all monsters on the field.

However, Ignister activated the trap A.I.Q, this trap forces Yusaku to control at most $$$K$$$ monsters.

Link monsters are powerful monsters, they depend on their locations to make links between each other. Two monsters $$$a$$$ and $$$b$$$ are called linked if at least one of the following is satisfied:

  • The distance between $$$a$$$ and $$$b$$$ is strictly less than $$$D$$$.
  • If $$$a$$$ is linked to $$$c$$$ and $$$b$$$ is linked to $$$c$$$, then $$$a$$$ and $$$b$$$ are linked.

Monsters that are linked are treated as one monster. For example: if Yusaku has $$$4$$$ monsters, $$$a$$$, $$$b$$$, and $$$c$$$ that are linked, and a monster $$$d$$$ which is not linked to any other monster, the $$$4$$$ monsters are treated as $$$2$$$, not $$$4$$$.

Yusaku wants to destroy some of his monsters (possibly none or all of them) such that the number of remaining monsters on the field is at most $$$K$$$. Help Yusaku find the maximum damage he can inflict to Ignister.

Input

The first line of the input contains an integer $$$T$$$ ($$$1 \le T \le 10^5$$$) denoting the number of test cases.

The first line of each test case contains three integers $$$n$$$, $$$K$$$, and $$$D$$$ ($$$1 \le K \le n \le 10^5$$$, $$$1 \le D \le 10^9$$$) — the number of monsters, the maximum number allowed for controlling monsters, and the linking distance.

The second line of each test case contains $$$n$$$ integers $$$x_1, \ldots, x_n$$$ ($$$1 \le x_i \le 10^9$$$) — the location of monsters. It is guaranteed that $$$x$$$ is strictly increasing.

The last line of each test case contains $$$n$$$ integers $$$p_1, \ldots, p_n$$$ ($$$-10^5 \le p_i \le 10^5$$$) — the power of monsters.

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

Output

For each test case, output the answer in a single line.

Example
Input
5
3 1 2
1 2 3
5 -2 5
3 2 2
1 2 3
5 -2 5
3 1 1
1 2 3
4 3 5
2 2 10
4 7
-7 -4
4 1 8
2 4 6 8
4 -10 -10 4
Output
8
10
5
0
8

J. Lazy Abdo
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

This is one of the main reasons why Da7doo7 gets fired a lot.

Da7doo7 always gets extremely frustrated with Tinky-Winky's laziness and decides to assign him some tasks. There are a total of $$$n$$$ tasks, the $$$i$$$-th of which requires a certain number of minutes denoted by $$$a_i$$$. Da7doo7 wants Tinky-Winky to handle $$$k$$$ of these tasks.

Your task is to select the $$$k$$$ tasks in a way that maximizes the amount of time Tinky-Winky spends on them. In other words, you need to choose the tasks that have the highest total time requirement, allowing Tinky-Winky to be occupied for as long as possible.

Help Da7doo7 by selecting the $$$k$$$ tasks that will keep Tinky-Winky busy for the maximum amount of time possible.

Input

The first line contains an integer $$$T$$$ $$$(1\le T\le 100)$$$ representing the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ $$$(1\le k \le n \le 100)$$$ — the number of all tasks and selected tasks respectively.

The last line of each test case contains $$$n$$$ integers $$$a_1, \ldots, a_n$$$ $$$(1\le a_i\le 1000)$$$ — the elements of array $$$a$$$.

Output

For each test case, output the maximum amount of time that Tinky-Winky will spend on the chosen tasks.

Example
Input
2
5 3
1 5 3 4 2
4 1
7 13 2 5
Output
12
13

K. Finding The Way Home
time limit per test
8 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Every time Da7doo7 gets fired he goes to a new tree and gets lost.

Da7doo7 is currently lost in the tree and needs to find his way back home, which is located at node $$$1$$$ the root. Each node in the tree has a corresponding value, denoted by $$$b_i$$$. There is also an array of length $$$n$$$ that represents the fun of the $$$i$$$-th day $$$a_i$$$.

Every day, Da7doo7 will go to an adjacent node on the path leading to the root. As he reaches a new node, his excitement level increases by adding the product of the node value of the current node $$$b_{\texttt{current node}}$$$ with the corresponding fun value of the current day $$$a_{\texttt{current day}}$$$.

For each possible starting node in the tree, your task is to calculate the total excitement that Da7doo7 can achieve by following the path to the root.

The above picture illustrates the example.

In summary, you need to determine the total excitement Da7doo7 can experience by selecting different starting nodes and following the path to the root modulo $$$998\,244\,353$$$.

Input

The first line contains a single integer $$$T$$$ $$$(1\le T\le 1000)$$$ denoting the number of test cases.

The first line of each test case contains an integer $$$n$$$ $$$(1\le n\le 3\cdot 10^5)$$$ indicating the number of nodes of the tree.

The second line of each test case contains $$$n$$$ integers $$$a_1, \ldots, a_n$$$ $$$(1\le a_i\le 10^9)$$$ — the fun of each day.

The third line of each test case contains $$$n$$$ integers $$$b_1, \ldots, b_n$$$ $$$(1\le b_i\le 10^9)$$$ — the value of each node.

Each of the following $$$n-1$$$ lines of each test case contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n, u \neq v$$$) — the vertices connected by an edge. It is guaranteed that these edges form a tree.

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

Output

For each test case, print $$$n$$$ lines, the $$$i$$$-th of which contains the answer which represents the total excitement Da7doo7 can experience if he started from node $$$i$$$ modulo $$$998\,244\,353$$$.

Example
Input
1
13
1 2 3 4 5 6 7 8 9 10 11 12 13
1 2 3 4 5 6 7 8 9 10 11 12 13
1 2
2 3
3 4
4 5
1 6
1 7
3 8
8 9
6 10
10 11
11 12
7 13
Output
1
4
10
20
35
8
9
24
47
25
53
93
30
Note

Considering the answer for starting position $$$11$$$: the path to the root is $$$11 \rightarrow 10 \rightarrow 6 \rightarrow 1$$$.

So the total excitement that Da7doo7 can achieve is: $$$b_{11}\cdot a_1 + b_{10}\cdot a_2 + b_6\cdot a_3 + b_1\cdot a_4 = 11\cdot 1 + 10\cdot 2 + 6\cdot 3 + 1\cdot 4 = 53$$$.

L. Circles
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Geo Ghaffar has become the boss and he didn't want to tell Da7doo7 "You're FIRED" so he told him "solve this problem or you're FIRED", knowing that Da7doo7 is bad at geometry. Of course Da7doo7 called you, his best friend, for help.

You are given $$$n$$$ distinct points in a $$$2D$$$ plane with integer coordinates. You will draw a finite circle in such a way it passes through the maximum number of points. Since you hate floating numbers, you only have to print this maximum number.

The above picture illustrates the first example. The green circle is the optimal choice to achieve the maximum number as it passes through all $$$4$$$ points, whereas the blue circle only passes through $$$2$$$ points.
Input

The first line of the input contains a single integer $$$T$$$ ($$$1 \le T \le 100$$$) representing the number of test cases.

For each test case, the first line contains a single integer $$$n$$$ ($$$2 \le n \le 200$$$) denoting the number of points. Each of the next $$$n$$$ lines contain two integers $$$x_i$$$ and $$$y_i$$$ ($$$-10^6 \le x_i, y_i \le 10^6$$$) — the coordinates of every point. It is guaranteed that the given points are distinct.

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

Output

For each test case, print the answer in a single line.

Examples
Input
1
4
0 1
1 0
0 0
1 1
Output
4
Input
1
30
-54 -27
-74 91
-74 33
-45 -73
15 20
-35 66
-27 -85
53 24
-79 -62
40 29
16 27
95 -79
60 63
-32 -44
-31 -69
100 1
-91 -59
80 -18
77 -5
-38 64
-68 -67
-94 97
31 -41
-39 97
42 40
6 -19
-92 -28
-80 -1
-21 11
-90 -45
Output
3

M. Captain Haddock And The Counting Problem
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Getting fired inspired Da7doo7 to start writing puzzles for kids but he didn't know how to solve this one.

Captain Haddock and Tintin were walking on the street leading to Marlinspike Hall, and suddenly the Captain said:

"Blue Blistering Barnacles!! since when there were $$$n$$$ people walking on this street?"

Captain Haddock is so tired after traveling all over the world, so can you help him count how many people were on the street apart from him and Tintin?

Input

The first line contains an integer $$$T$$$ ($$$1 \le T \le 100$$$) denoting the number of test cases.

Each of the following $$$T$$$ lines contains an integer $$$n$$$ $$$(2\le n \le 100)$$$ — the number of people on the street.

Output

For each test case, print the number of people that were on the street apart from Captain Haddock and Tintin in a single line.

Example
Input
2
5
2
Output
3
0

N. Fixing The Servers
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Da7doo7 was working for Telekilogram(the bigger Telegram) but he broke the server and got fired.

As the Telekilogram servers are going down, you and your classmates started to panic. Luckily, Telekilogram decided that every connected group of people should register a group account.

What is a group account? It is a way to solve the problem since a group of $$$n$$$ people needs to stay connected. The group account provides them with $$$n-1$$$ connections where in each connection, person $$$x$$$ and person $$$y$$$ can chat together. The purpose of the group account is to keep everyone connected using the least amount of server power.

The $$$i$$$-th student has a value $$$a_i$$$ that explains his interests and personality. Using this number, the compatibility of two students $$$x$$$ and $$$y$$$ is $$$\gcd(a_x, a_y)$$$. For example: if student $$$x$$$ has the value $$$12$$$ and student $$$y$$$ has the value $$$18$$$ then their compatibility is $$$6$$$.

Your class knows that you are the best problem solver, so they asked you to assign the connections in such a way that the sum of compatibilities is maximized. Given that all members in your class have values at most $$$m$$$, please, help them resolve this issue.

Input

The first line contains a single integer $$$T$$$ $$$(1\le T\le 2000)$$$ representing the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ $$$(1\le n\le 5\cdot 10^5, 1\le m \le 10^6)$$$ — the size of the class and the maximum value possible of all members.

The last line of each test case contains $$$n$$$ integers $$$a_1, \dots, a_n$$$ ($$$1\le a_i \le m$$$) — the value of each member of the class.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5\cdot 10^5$$$, as well as the sum of $$$m$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each test case, print a single integer denoting the maximum sum of compatibilities that can be achieved.

Example
Input
3
3 10
2 6 8
2 2
1 2
4 4
1 2 3 4
Output
4
1
4