Floor Tiles
Input: standard input
Output: standard output
Time Limit: 2 seconds

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.

You will be given K, the number of test cases. The next K lines will contain four positive integers separated by spaces: L1 L2 W1 W2, 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 Jack’s Kitchen. A 2x1 kitchen is different from a 1x2 kitchen.

Sample Output

1
2

Problem setter: - Yin Zhao (aka Bugz Podder)

Thanks to Derek Kisman for his alternate solution.

"~~ Pretend we like math: don’t drink and derive ~~"