Alice and Bob are superhumans. They have w1 and w2 weights respectively. Both of them own a complete binary tree with n1 and n2 nodes respectively. Now they want to traverse every node of their respective trees as they want to loose some weight. During traversal of every edge first time, they will loose some weight (may be one or more units, but at least one unit). But when they will traverse same edge again they won't loose any weight. So after loosing some weight during first time traversal of an edge, they can traverse same edge any number of times without loosing any weight. ( So if they decide to traverse edge a-b, first time they will loose some weight, but after that whether they come back from b to a or they traverse again a to b, they won't loose any weight). Now we all know how much alice and bob love playing games. So they challenged each other to tell the number of ways to traverse their respective tree such that they are left with only 1 unit weight, means alice have to tell no of ways in which alice can travel tree with n1 nodes (she will have to traverse each and every edge of tree) such that she is left with only 1 unit weight and bob have to tell no of ways in which bob can traverse tree with n2 nodes such that he is left with just 1 unit of weight. No of ways can be very large, so they both have to report their answers mod 1000000007 (10^9 + 7). Alice and bob are smart enough to solve this problem. So they both correctly reported their respective desired answers. Let there answers be x and y respectively. Now they started playing another game. Now they have an infinite number line. Alice and bob are standing on number line on points x and y respectively. Now they will start making moves alternatively. First move will be made by alice and then they will make moves alternatively. When it is alice's turn she will either pass move to bob or she will move 'x' points in left direction (negative) or 'x' points in right direction (positive). Similarly when it is bob's turn he will either pass move to alice or he will move 'y' points in left dirction (negative) or 'y' points in right dirction (positive). They are keeping track of their progress on a common screen. Screen initially displays '0'. Number on screen will be updated after every move. For example in alice's turn, if she pass her move to bob, then number on screen will remain unchanged, if she make 'x' moves in left direction 'x' will be subtracted from number on screen, if she make 'x' moves in right direction 'x' will be added to the number currently on screen. Similar is the case for bob). They will stop playing when number on screen will become 'z' where 1<=z<=x and z divides x, 1<=z<=y and z divides y. If more than one values for z are possible, select largest one. They are also keeping track of no of moves/turns made by both players and they want to minimize total no of moves made by players. You can assume that both players play optimally to minimize total no of moves and it is always possible to get 'z' on screen. You will be given n1 and n2, no of nodes in both trees and w1, w2 weight of alice and bob respectively in input and you have to tell no of steps made by alice and bob in final number line game. Since the number of steps can be very large output the answer mod 1000000007. Note that when a player pass move to another player, this move is not counted in total no of moves/turn which they have to minimize. Only when they move x/y/-x/-y is counted.

** NOTE: ** Two traversals will be considered different if weight lost on at least one edge in those two traversals is different. For example if tree has 3 nodes 1,2,3 one is root and 2 is left child. Then for different traversals we will see weight lost on both edges (1-2), (1-3) and these will be counted different if weight lost on at least one edge is different.

Input: First line will contain t, number of test cases. First line of every test case contain two integers w1 and w2. Second line will contain two integers n1 and n2.

Output: For every test case you have to output single integer as explained.

Constraints:

3<=w1,w2<=10^6

2<=n1,n2<=10^6

w1>n1

w2>n2

1<=t<=10