小苯的地下城寻宝

题号：NC286293
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

小苯来到了一个地下城，地下城有 $n$ 个房间。

除了小苯目前所在的位于地下一层的 $1$ 号房间外，其余所有房间都恰好有一个更高一层楼的房间和他之间有一条双向道路。形式化的：对于所有 $i\ (2 \leq i \leq n)$ 号房间，记 $i$ 号房间位于地下第 $d$ 层，则一定恰好存在一个位于第 $d-1$ 层的 $j$ 号房间，使得 $i$ 和 $j$ 号房间之间存在一条双向道路。

地下城的每个房间内都有一些宝藏， $i$ 号房间的宝藏数量为 $a_i$ 。

现在小苯已经决定了要带走 $1$ 号房间的宝藏，同时他还会再选择一些其它房间中的宝藏带走，同时满足以下的所有条件：

$\bullet$ 每个房间中的宝藏要么全拿走要么全部不拿，不能只拿走一部分。
$\bullet$ 每一层楼至多只能有一个房间的宝藏被拿走。
$\bullet$ 将拿走的宝藏数量的按照房间的楼层深度排序，要满足任意相邻的两个宝藏数量都不互素（即 $gcd>1$ ）。

只有满足了以上的所有条件，小苯才可以把选择的宝藏全部带走，否则小苯一个宝藏都带不走。
现在小苯想要问问你，有多少种不同的宝藏选择方式能让他带走他所选的宝藏们呢，请你帮帮他吧。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：
第一行一个正整数  表示地下城中房间的个数。
第二行  个正整数 ，表示每个房间的宝藏数量。
第三行  个整数 ，表示第  号房间上层的房间是 ， 和  号房间之间有一条双向道路。
（保证 ，即  号房间不存在上层房间。）
（保证所有测试数据中， 的总和不超过 。）

输出描述:

对于每组测试数据，在单独的一行输出一个整数表示小苯的合法选择方案个数。
（由于结果可能很大，因此只需要输出答案对  取模的值。）

示例1

输入

复制

输出

复制

9
1

说明


样例 1 中的地下城如图，共有三层，五个房间，其中所有房间的宝藏数量均为 。
合法的宝藏拿取方案有（以下数字为拿走宝藏的房间编号）：
，，，，，，，， 这  种。

样例二则只有一种方案，即拿走一号房间的宝藏后，无法再拿走任何宝藏，因此只有： 一种。