Aleksei received an apple tree of size $n$ as a birthday present. As a competitive programmer himself, he decided to calculate the number of $k$-apple pies on the tree.
An apple tree of size $n$ is defined as a rooted tree with $n$ vertices, rooted at vertex $1$, where each vertex has strictly fewer direct children than its parent (except the root that doesn't have any parent).
A $k$-apple pie is a pair $(v, S)$ where:
- $v \in V$ is a vertex of the tree (the center),
- $S \subset V \setminus \{v\}$ is a set of vertices of size $k - 1$,
- there exists an integer $d$ such that for every $u \in S$, $\text{dist}(v, u) = d$.
The distance $\text{dist}(u, v)$ is defined as the number of edges on the simple path between vertices $u$ and $v$.
In other words, a $k$-apple pie consists of one vertex $v$ (the center) and $k - 1$ other vertices that are all at the same distance from $v$.
Your task is to compute the number of $k$-apple pies in the given tree.
Since the answer may be large, output it modulo $998\,244\,353$.
Input
Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
Each test case begins with a line containing two integers $n$ and $k$ ($2 \le n \le 5 \cdot 10^5$, $1 \le k \le n$): the number of vertices in the apple tree and the size of the apple pie.
The next line contains $n - 1$ integers $p_2, p_3, \dots, p_n$ ($1 \le p_i < i$), where $p_i$ denotes the parent of vertex $i$ in the apple tree.
The sum of $n$ over all test cases does not exceed $5 \cdot 10^5$.
Output
For each test case, output a single integer: the number of $k$-apple pies modulo $998\,244\,353$.
Examples
Input 1
3 3 3 1 1 5 2 1 1 2 3 6 3 1 1 1 2 2
Output 1
1 20 16
Note
In the first test case, the only existing pie is centered at vertex $1$, and the corresponding set is $S = \{2, 3\}$.