夏天快要到了，去兴绍奶龙山参加 ION5202 的 0p 决定探究奶龙山的性质。
奶龙山内部存在复杂的奶龙山隧道，但是聪明的 0p 一眼就看出了 条奶龙山隧道的结构是一颗树。其中任意两个隧道只在 个休息点处相交，两两休息点之间都有路径联通，第 个休息点有一个权值 ，对于每一个素数 ，若 则说明 公司参与了休息点建设。想要经过一个休息点，就必须和所有参与了休息点建设的公司搞好关系。
0p 有 条心仪的路线，第 条是从休息点 走到休息点 ，对于每一条路线，0p 想知道，他需要与多少公司搞好关系才可以成功地走完这一条路线。
请注意算法常数对时间效率的影响。
