Floor Tiles

Jack is building a new house. He would like to tile his kitchen with congruent pieces formed by removing a 1×1 square from a 2×2 square. He already knows that his kitchen will have length between L1 and L2 inclusive, and its width will be between W1 and W2 inclusive. Jack insists his kitchen to be a perfect rectangle. Of course, the floor must be tiled completely using these pieces (no overlaps, no spaces). Determine the number of dimensions for Jack’s Kitchen. Input You will be given K, the number of test cases. The next K lines will contain four positive integers separated by spaces: L1 L2 W 1 W 2, all of which are less than 1000. Output For each test case you are to output a single line containing the number of different dimensions for Jacks Kitchen. A 2×1 kitchen is different from a 1×2 kitchen. Sample Input 2 2223 2334 Sample Output 1 2