小红有一棵节点总数为 的无根树。 一个结点作为根节点的时候，必须满足除该结点以外的所有结点的因子个数都要小于等于其父结点的因子个数的两倍。 小红想知道有多少个结点可以作为根节点。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数 代表数据组数，每组测试数据描述如下：第一行输入一个整数  代表树上的节点数量。第二行输入  个整数  代表每一个节点的权值。此后 行，第 行输入两个整数 和 表示树上第 条边连接节点 和 。保证树联通，没有重边。除此之外，保证所有的 之和不超过 。

输出描述:

对于每一组测试数据，在一行上输出一个整数，代表可以作为根节点的个数。