SP32093 WTFM - Where The Friends Meet!

Blackhood、Kira 和 BaZ 是一对非常要好的朋友。经过一段不算太长的时间，他们决定要见面。这个国家有 $N$ 座城市，每座城市都有一个 GDP 值（值可以重复）。国家的道路网络很特别，任意两个城市之间只能通过一条道路相连。Kira 和 Blackhood 决定在他们各自城市的唯一路径上的某个城市见面（包括他们所在的城市）。但 BaZ 对此有些挑剔，他要求必须是那些 GDP 至少有 $K$ 个不同质因数的城市才愿意去。因此，你的任务是，给定 Blackhood 和 Kira 的家乡城市，计算出他们可以在此之间的路径上找到多少个符合 BaZ 条件的城市。

输入包含多组测试数据。每组测试数据的第一行包含三个整数：$N$、$K$ 和 $Q$，分别表示城市数量、BaZ 喜欢的数字需要至少有的不同质因数的数量，以及查询的数量。 接下来一行由 $N$ 个整数构成，代表每个城市的 GDP。 之后的 $N-1$ 行中，每行包含两个整数 $u$ 和 $v$，表示城市 $u$ 和城市 $v$ 之间有一条道路连接。 接下来的 $Q$ 行，每行包含两个整数 $a$ 和 $b$，表示一个查询，询问在城市 $a$ 和城市 $b$ 之间的路径上，有多少个城市的 GDP 满足 BaZ 的条件。

对于每个查询，输出一行表示符合条件的城市数量。

- $1 \leq N, Q \leq 10^5$ - $1 \leq K \leq 10$ - $1 \leq \text{GDP} \leq 10^{12}$ **本翻译由 AI 自动生成**