C. 排列组合

老师教大家排列组合，cqh 觉得很简单，老师决定考验一下 cqh 的反应能力，从几个东西里选几个的基础题当然难不倒 cqh，所以老师决定出一道更难的题目考 cqh：

假设现在有 块石头，和很多条线，每条线连接两块石头，一条线只有在它连接的两块石头都没被选择的情况下可以被选择，挑选一条线时必须同时挑选被它所连接的两块石头，现在老师想知道挑选其中 条线以及因为被这 条线连接而被同时挑选的 块石头有多少种挑选方式。说好考反应能力所以绳子的数量会变动，老师会说+ u v就是加一条连接 和 的绳子，老师说- u v就是减少条连接 和 的绳子。若连接 和 的有多条绳子，挑选不同的绳子算不同的方式，每次减少绳子保证绳子至少存在一条。

不幸的是，这道题非但没能考倒 cqh，反而被他拿来考你。

第一行为测试的组数 。

对于每组测试数据，第一行为整数 。

接下来的行, 每行一句加减绳子的指令, 满足。

对于每句指令，输出一行 个数字。

其中第 个数字表示当前情况下挑 条线以及因为被这 条线连接而被同时挑选的 块石头的方式数。

由于答案可能很大，所以我们将答案对 取模。

样例输入

1
4 8
+ 1 2
+ 3 4
+ 1 3
+ 2 4
- 1 2
- 3 4
+ 1 2
+ 3 4

样例输出

1 0
2 1
3 1
4 2
3 1
2 1
3 1
4 2