#10078. [Sleeping Cup #7] C. Garbage Collection

Sleeping Cup 王国共有 个垃圾站，其中 号垃圾站是总垃圾站，而 号垃圾站都是分垃圾站。每个分垃圾站都有恰好一个编号小于自己的直接上级垃圾站。

这天上午，Sleeping Goose 查看了所有垃圾站的监控，数出了每个垃圾站目前堆放的垃圾袋数（均为不大于 的正整数），并决定让它的员工们对所有垃圾站进行一次大清理。

根据 Sleeping Goose 对员工们的上岗培训内容，Sleeping Goose 需要提供一个操作序列 并保证 ，而员工们需要升序枚举 并对每个 执行以下操作：

• 如果 ，什么都不做。
• 否则，将 号垃圾站中的所有垃圾运送到它的直接上级垃圾站。

员工们完成任务后， 号垃圾站中的所有垃圾将被 Sleeping Goose 亲自拉到垃圾处理厂集中处理。

不幸的是，就像题目背景中说的那样，这些员工经常玩忽职守 —— Sleeping Goose 越让他们干活，他们就越要摸鱼。具体来说，员工们实际上会升序枚举 并对每个 执行以下操作：

• 如果 ，什么都不做。
• 如果 号垃圾站中目前存放的垃圾袋数不大于 ，什么都不做。
• 如果以上两个条件都不满足，保留 号垃圾站中的 袋垃圾，并将剩下的垃圾运送到它的直接上级垃圾站。

尽管如此，Sleeping Goose 还是希望能在这次大清理中用尽量短的时间清理尽量多的垃圾。

为了帮助 Sleeping Goose，你需要回答以下三个问题：

1. Sleeping Goose 在这次大清理中最多能清理多少袋垃圾？
2. 在清理垃圾最多的前提下，Sleeping Goose 给员工们的操作序列至少要包含多少项？
3. 在清理垃圾最多且（在清理垃圾最多的基础上）操作序列最短的前提下，Sleeping Goose 一共有多少种本质不同的清理方案可供选择？

• 第一个问题的答案不取模。
• 第二个问题的答案不取模。
• 第三个问题的答案对 取模。

本题有多组数据。

第一行输入一个整数 ，表示测试数据的数量。

对于每组测试数据：

行，每行两个正整数 ：

• 表示 号垃圾站的直接上级垃圾站编号，其中 ，。
• 表示 号垃圾站中目前堆放的垃圾袋数，其中 。
• 特别地，（也就是说，第一行输入的两个正整数实际上是 和 ）。

对于每组数据，输出一行三个整数，表示题目描述中三个问题的答案：

• 第一个问题的答案不取模。
• 第二个问题的答案不取模。
• 第三个问题的答案对 取模。

样例输入 #1

2
1 1
2 1
1 1

样例输出 #1

1 0 1
1 0 1

样例输入 #2

2
6 6
1 2
1 2
2 3
2 3
2 3
13 10
1 1
2 2
3 3
2 4
3 2
4 3
3 4
4 5
5 3
4 4
5 5
6 6

样例输出 #2

8 2 3
14 3 1

样例 2 解释

对于第一组数据，最优的 种清理方案如下：

• 清理 号垃圾站中的某一个（因此一共有 种清理方案），运走 袋垃圾，保留 袋垃圾，使得 号垃圾站堆放的垃圾袋数变为 。
• 清理 号垃圾站，运走 袋垃圾，保留 袋垃圾，使得 号垃圾站堆放的垃圾袋数变为 。

这 种清理方案对应的操作序列分别是 。

请注意，以下 种清理方案虽然满足第一个问题的前提，但不满足第二个问题的前提，因此没有计入第三个问题的答案：

• 清理 号垃圾站中的某一个（此处有 种选择方案），运走 袋垃圾，保留 袋垃圾，使得 号垃圾站堆放的垃圾袋数变为 。
• 清理 号垃圾站中的另一个（不能是刚刚清理过的那个，此处有 种选择方案），运走 袋垃圾，保留 袋垃圾，使得 号垃圾站堆放的垃圾袋数变为 。
• 清理 号垃圾站，运走 袋垃圾，保留 袋垃圾，使得 号垃圾站堆放的垃圾袋数变为 。

对于第二组数据，唯一一种最优清理方案对应的操作序列是 。

数据范围

对于 的数据，，。

本题共有四个等分的子任务，各子任务的特殊限制如下：

1. 保证 。
2. 对于 保证 。
3. 对于 保证 。
4. 无特殊限制。