该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

现有A,B两堆石子，初始时分别有\(s_A, s_B\)粒。每次可以执行如下两种操作之一：
（1）将A堆中一半（向下取整，下同）的石子加到B堆中，然后在A堆上补加一粒石子；
（2）将B堆中一半的石子加到A堆中，然后在B堆上补加一粒石子。
要求若干次操作之后，两堆的石子数分别变为\(t_A, t_B\)，求共有多少种操作方案。

I/O格式

输入

第一行是一个正整数\(T\)，表示数据的组数；
之后\(T\)行，每行一组测试数据，包含4个正整数\(s_A, s_B, t_A, t_B\)，保证\(s_A, s_B, t_A, t_B \ge 2\)。

输出

每组数据输出一行，方案数对\(10^5 + 3\)取模后的结果。

样例

输入

3
3 6 9 6
4 15 9 16
2 100 50 58

输出

8
4
1

数据规模及约定

50%的数据：\(2 \le s_A, s_B, t_A, t_B \le 10\)
100%的数据：\(T \le 10, \quad 2 \le s_A, s_B, t_A, t_B \le 1000\)
时间限制1s，空间限制256MB。