Mr. Walker\text{Mr. Walker}Mr. Walker最近在研究树，尤其是最长树链问题。现在树中的每个点都有一个值，他想在树中找出最长的链，使得这条链上对应点的值的最大公约数不等于111。请求出这条最长的树链的长度。

第一行一个整数 nnn，表示点的个数。

接下来n−1n-1n−1行，每行两个整数x,yx,yx,y表示x,yx,yx,y之间有边。

数据保证给出的是一棵树。

接下来一行nnn个整数表示每个点对应的权值 aia_iai

输出一个整数，表示这条树链的长度。

1≤n≤1000001 \leq n \leq 1000001≤n≤100000

1≤ai≤1091 \leq a_i \leq 10^91≤ai≤109