你有一棵以 $1$ 为根的有根树。

第 $i$ 个点上有一个非负整数 $c_i$ 和一个正整数 $d_i$。你可以进行若干次如下操作：

• 选择一个点 $u$，满足 $c_i$ 不是 $d_i$ 的倍数。然后令 $u$ 到根上的所有数的 $c_i$ 增加 $1$。

求执行完这些操作后，本质不同的 $c$ 数组的个数对 $998244353$ 取模的结果。

输入格式

第一行包含一个整数 $n$。

接下来 $n$ 行，第 $i$ 行两个整数 $c_i,d_i$。

接下来 $n-1$ 行，第 $i$ 行两个整数 $u_i,v_i$，表示一条边。

输出格式

输出包含一个整数，表示本质不同的 $c$ 数组的个数对 $998244353$ 取模的结果。

样例 1

input

2
0 2
1 2
1 2

output

3

数据范围

设 $m$ 为距离根最远的点到根的距离。

特殊性质 A：保证对于 $2\le i\le n$，点 $i$ 在有根树上的父亲在 $1\sim i-1$ 中等概率随机生成。

对于所有数据，$1\le n\le 2000$，$0\le c_i\le 10^9$，$1\le d_i\le 10^9$。

时间限制：$\texttt{1.8s}$

空间限制：$\texttt{256MB}$