有一棵 个节点的有根树，树上节点编号从 至 ，树的根节点是 。 Rainbow 在点 ，Flower 在点 ，定义函数 为点 到点 的最短距离，即从 到 需要经过的最短的边数。 Rainbow 想要与 Flower 相遇，相遇的过程需要代价，定义代价函数 ，其计算方式如下： 若 或 ，Rainbow 可以开启传送，直接到达 Flower 的位置，此时代价函数 ； 否则无法开启传送，此时代价函数 ，其中 为 和 的最近公共祖先。 Rainbow 与 Flower 在树上嬉戏，他们体验了各种 组合，但嬉戏的过程中忘记了计算代价函数 ，现在请你帮助他们计算所有 的代价。 由于所有的 组合数量过多，你只需要告诉他们所有组合的代价函数 之和即可。即求解对于所有的 的 之和： 。 由于答案可能很大，请将答案对 取模后输出。 【名词解释】 最近公共祖先：在一棵有根树中，节点 和 的最近公共祖先指同时位于“根到 的路径”和“根到 的路径”上的节点中，距离根节点最远的一个。

输入描述:

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

输出描述:

对于每一组测试数据，新起一行输出一个整数，表示所有组合的代价函数  之和对 取模后的结果。