Little RK's birthday is coming soon. All of his friends has already decided what they will do for the grand celebration of their friend's birthday. The decoration part of party room is taken by quantum ,a historical guy. He wants decoration part to be perfect so he wants to start his work from today. For this he has brought two types of balloons that is P red balloons and Q green balloons.

He wants to stick all balloons on the wall in a row. But as you know their is always problem of similar colours. Quantum thought that putting many similar colour balloons together is not a good idea as the arrangement may not look beautiful then. So he decided that he will stick at most X red balloons consecutively one after another and at most Y green balloons consecutively one after another. Now he thought that their are many possible ways to stick balloons on the wall following the above procedure. So first he wants to know how many ways are their to stick balloons on the wall then he will choose the most beautiful arrangement. Note that quantum must stick all balloons in each of his arrangement.

INPUT :

The first line contains the number of test cases T(1<=T<=10). Each test case consists of four space-separated integers P,Q,X,Y (1<=P,Q<=1000,1<=X,Y<=10).

OUTPUT :

For each test case output the required number of ways modulo 179424673.