Chiaki 发现了一个有趣的石子游戏：两名玩家从两堆非空的石子开始。在每一轮中，玩家可以选择一堆石子数量为偶数的堆，并将该堆中一半的石子移动到另一堆中。如果玩家无法移动，或者游戏达到了之前出现过的状态，则游戏结束。在前一种情况下，无法移动的玩家输掉比赛。在后一种情况下，游戏被判定为平局。

给定两个正整数 $n$ 和 $m$，Chiaki 想知道有多少对 $(a, b)$ ($1 \le a \le n, 1 \le b \le m$) 满足：如果初始时两堆石子分别有 $a$ 和 $b$ 个，那么先手玩家有必胜策略，或者游戏以平局结束，或者后手玩家有必胜策略。由于这个数字可能非常大，你只需要计算其对 $10^9 + 7$ 取模的结果。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据的组数。对于每组测试数据：

第一行包含一个二进制字符串 $s$ ($1 \le |s| \le 10^6$)，表示 $n$ 的二进制表示（无前导零）。

第二行包含一个二进制字符串 $t$ ($1 \le |t| \le 10^6$)，表示 $m$ 的二进制表示（无前导零）。

保证所有测试数据中二进制字符串的长度之和不超过 $2 \times 10^6$。

输出格式

对于每组测试数据，输出三个整数：分别表示先手获胜、平局以及后手获胜的对数 $(a, b)$。

样例

输入 1

3
111
111
1111
1111
10101010
1001010

输出 1

8 24 17
41 116 68
2546 6689 3345

说明

对于第一个样例：

• 先手获胜的对数：(2, 2), (2, 4), (2, 6), (4, 2), (4, 6), (6, 2), (6, 4), (6, 6)。
• 平局的对数：(1, 2), (1, 4), (1, 6), (2, 1), (2, 3), (2, 5), (2, 7), (3, 2), (3, 4), (3, 6), (4, 1), (4, 3), (4, 5), (4, 7), (5, 2), (5, 4), (5, 6), (6, 1), (6, 3), (6, 5), (6, 7), (7, 2), (7, 4), (7, 6)。
• 后手获胜的对数：(1, 1), (1, 3), (1, 5), (1, 7), (3, 1), (3, 3), (3, 5), (3, 7), (4, 4), (5, 1), (5, 3), (5, 5), (5, 7), (7, 1), (7, 3), (7, 5), (7, 7)。