H. Tree Or Not Tree
time limit per test
6 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given a tree consisting of $$$N$$$ vertices numbered from $$$1$$$ to $$$N$$$. The tree has $$$N-1$$$ weighted edges, where the $$$i$$$-th edge connects vertices $$$u_i$$$ and $$$v_i$$$ and has a weight $$$w_i$$$ ($$$1 \le w_i \le M$$$).

Let $$$S$$$ be the set of all simple paths in the tree that contain at least one edge. A simple path can be uniquely identified by its unordered pair of distinct endpoints $$$(u, v)$$$ ($$$1 \le u \lt v \le N$$$). Thus, there are exactly $$$|S| = \frac{N(N-1)}{2}$$$ paths in the set $$$S$$$. Each path $$$x \in S$$$ can be viewed as a set of edges.

For any two paths $$$x, y \in S$$$, we denote $$$x \cap y$$$ as the set of edges that are common to both paths. We define a cost function $$$f(x, y)$$$ as follows:

$$$$$$f(x, y) = ( \sum_{e \in x \cap y} w_e ) \cdot \gcd_{e \in x \cap y}(w_e)$$$$$$

I.e.: the value of a function is the sum of the weights on the intersection path of $$$x$$$ and $$$y$$$ times the GCD of the weights on the intersection path of $$$x$$$ and $$$y$$$, where $$$\gcd(i, j)$$$ is the greatest common divisor of $$$i$$$ and $$$j$$$.

Your task is to calculate the total sum of $$$f(x, y)$$$ over all ordered pairs of paths $$$(x, y)$$$ from the set $$$S$$$.

Since the total sum can be very large, output it modulo $$$998244353$$$.

Input

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

The description of the test cases follows.

The first line of each test case contains two space-separated integers $$$N$$$ ($$$1 \le N \le 10^5$$$) and $$$M$$$ ($$$1 \le M \le 10^5$$$) — the number of vertices in the tree and the maximum possible edge weight.

Each of the next $$$N-1$$$ lines contains three space-separated integers $$$u_i$$$, $$$v_i$$$, and $$$w_i$$$ ($$$1 \le u_i, v_i \le N$$$, $$$u_i \neq v_i$$$, $$$1 \le w_i \le M$$$) — meaning there is an edge between vertices $$$u_i$$$ and $$$v_i$$$ with weight $$$w_i$$$.

It is guaranteed that the given edges form a valid tree, and the sum of $$$N$$$ and the sum of $$$M$$$ over all test cases does not exceed $$$10^5$$$.

Output

For each test case, print a single integer — the total sum of $$$f(x, y)$$$ for all ordered pairs of distinct paths $$$(x, y)$$$, modulo $$$998244353$$$.

Example
Input
3
4 10
1 2 4
2 3 6
3 4 8
5 15
1 2 5
1 3 7
2 4 3
2 5 9
3 20
1 2 2
2 3 3
Output
904
2080
44
Note

In the third test case, the tree consists of $$$N = 3$$$ vertices and has two weighted edges: $$$(1, 2)$$$ with weight $$$2$$$, and $$$(2, 3)$$$ with weight $$$3$$$.

There are exactly $$$|S| = \frac{3 \cdot (3 - 1)}{2} = 3$$$ simple paths containing at least one edge:

  • $$$P_{1}$$$ with endpoints $$$(1, 2)$$$ containing the edge set $$$\{\,(1, 2)\,\}$$$.
  • $$$P_{2}$$$ with endpoints $$$(2, 3)$$$ containing the edge set $$$\{\,(2, 3)\,\}$$$.
  • $$$P_{3}$$$ with endpoints $$$(1, 3)$$$ containing both edges $$$\{\,(1, 2), (2, 3)\,\}$$$.

We calculate the function $$$f(x, y) = \left(\sum_{e \in x \cap y} w_e\right) \cdot \gcd_{e \in x \cap y}(w_e)$$$ for all $$$3 \times 3 = 9$$$ ordered pairs of paths:

  • For identical pairs ($$$x = y$$$):
    • $$$f(P_1, P_1) = 2 \cdot \gcd(2) = 4$$$
    • $$$f(P_2, P_2) = 3 \cdot \gcd(3) = 9$$$
    • $$$f(P_3, P_3) = (2 + 3) \cdot \gcd(2, 3) = 5 \cdot 1 = 5$$$
  • For distinct overlapping pairs ($$$x \neq y$$$):
    • $$$f(P_1, P_3) = f(P_3, P_1) = 2 \cdot \gcd(2) = 4$$$ (the common edge is $$$(1, 2)$$$)
    • $$$f(P_2, P_3) = f(P_3, P_2) = 3 \cdot \gcd(3) = 9$$$ (the common edge is $$$(2, 3)$$$)
    • $$$f(P_1, P_2) = f(P_2, P_1) = 0$$$ (no common edges)

Summing these values together gives: $$$$$$4 + 9 + 5 + 4 + 4 + 9 + 9 + 0 + 0 = 44$$$$$$ Thus, the total sum for the third testcase is $$$44$$$.