Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×
H. Chemical Reaction
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

The Bangladesh Advanced Pharmaceutical Systems (BAPS) is working with the Institute for Chemical Process Control (ICPC) to study how chemicals react inside a special chamber.

The chamber works in a very simple way. At the start, the scientists put some basic chemicals into it. Each second, the chemicals in the chamber are allowed to react spontaneously. Whenever two chemicals $$$x$$$ and $$$y$$$ are capable of reacting with one another, they produce a new chemical $$$z$$$. The chamber's conditions prevent $$$x$$$ and $$$y$$$ from reacting to completion, so both remain present and available for further reactions in subsequent seconds, while the newly formed chemical $$$z$$$ is added to the mixture. Each reaction takes exactly one second to complete, and multiple reactions can occur simultaneously in the chamber during the same second, as long as the required chemicals are present.

At the beginning, BAPS places $$$n$$$ different chemicals into the chamber. The scientists have identified $$$m$$$ pairs of chemicals that can react with one another, along with the resulting chemical produced from each reaction. Each reaction is described by three integers $$$x$$$, $$$y$$$, and $$$z$$$, indicating that chemicals $$$x$$$ and $$$y$$$ can react to produce chemical $$$z$$$.

Now, the scientists are interested in determining how many different chemicals can be present in the chamber after $$$10^{100}$$$ seconds. Since they cannot wait that long, they have asked you to figure it out.

Input

The first line of the input contains a single integer $$$t$$$ ($$$1 \leq t \leq 500$$$) — the number of test cases.

The first line of each test case contains two space-separated integers $$$n$$$ and $$$m$$$ ($$$1 \leq n, m \leq 1000$$$) — the number of different chemicals initially placed in the chamber and the number of reaction rules, respectively.

The second line of each test case contains $$$n$$$ space-separated integers $$$c_1, c_2, \ldots, c_n$$$ ($$$1 \leq c_i \leq 10^9$$$) — the types of chemicals initially placed in the chamber. It is guaranteed that all $$$n$$$ initial chemicals are distinct.

The next $$$m$$$ lines each contain three space-separated integers $$$x$$$, $$$y$$$, and $$$z$$$ ($$$1 \leq x, y, z \leq 10^9$$$, $$$x \lt y, x \ne z, y \ne z$$$) — indicating that chemicals $$$x$$$ and $$$y$$$ can react to produce chemical $$$z$$$. It is guaranteed that all $$$m$$$ reaction rules are distinct.

Output

For each test case, output a single integer in a line — the total number of different chemicals that can be present in the chamber after $$$10^{100}$$$ seconds.

Example
Input
2
2 3
1 4
1 4 2
2 4 3
1 3 6
2 2
1 1000000000
1 1000000000 500000000
500000000 1000000000 999999999
Output
5
4