该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给你一棵有$\red{n}$个结点的树，根节点为$\red{1}$定义$\red{f(x)=\prod_{i=1}^{n}{lca(x,i)}}$

其中$\red{lca(u,v)}$表示$\red{u}$和$\red{v}$的最近公共祖先。现在给你一些询问，对于每一个询问$\red{x，}$请求出$\red{f(x)}$的末尾有几个$\red{0}$。

输入格式

第一行包含两个整数$\red{n，}$$\red{q}$分别表示树的结点个数和询问个数；

接下来$\red{n-1}$行，每行包含两个整数$\red{u，}$$\red{v}$表示$\red{u}$和$\red{v}$之间有一条无向边（保证给出的是一棵树）；

接下来一行包含$\red{q}$个整数，每个整数代表了一个询问$\red{x}$。

输出格式

对于每次询问，输出一行包含一个整数表示询问的答案。

样例

输入样例

5 5
2 3
5 4
2 5
1 5
1 2 3 4 5

输出样例

0
2
1
2
0

提示

对于$\red{100\%}$的数据，$\red{1<=q<=n<=10^5,1<=u,v<=n }$

其中$\red{20\%}$的数据满足$\red{1<=q<=n<=10}$;

另有$\red{40\%}$的数据满足$\red{1<=q<=n<=1000}$。