小明去数字王国旅行，数字王国一共有n个部落，国王每年都需要部落进行交税，每个部落都有一个标号c_i，部落征税的税率刚好是标号c_i的因子的个数k_i。

国王还给王国建了n-1条路，保证所有的部落的互通，国王引用了上古秘法，在建设i到j的道路长度刚好是c_i和c_j的最大公约数，p到部落i距离为dis(p,i)，而部落需要给国王交税的费用是k_i \times dis(p,i) 。

国王想请小明计算下，如果国王要征最少的税，应该把王宫设在那个位置（如果有多个，请你选择最小的），和最少的税款

一个数字n；

第二行，n个数字c_i，用来表示国王给部落的标号；

接下来n-1行，每行2个数字u,v;

一个数字p表示王国所在地，一个数字ans表示最少的税款

样例说明：

如果设在1处，我们会发现总和s=2\times (2+3+3)+4 \times 6

如果设在4处，我们会发现总和s=5\times 4+2 \times 2+4\times (2+3)

所以设在1处比较合适。

数据范围：

20%数据,n \leq 10, c_i \leq 10

50%数据,n \leq 1000, c_i \leq 1000

100%数据,n \leq 10000, c_i \leq 10000