Business Cards

Time limit1sMemory limit512 MB

Summary
Decide whether a c x d sheet can be tiled exactly by axis-aligned a x b rectangles that may be rotated, for up to 1e5 cases.
Level

Medium7 of 10

Topics
Math, Number theory, Geometry, Implementation
Solved
No attempts yet

Problem

Running a paper shop is not an easy job, especially with demanding customers. Today the customers brought their own rectangular sheets of paper and asked you to cut each sheet into rectangular business cards of a fixed size. On top of that, they insist that all of the paper is used — not even a tiny scrap may be left over. The clever idea of cutting the sheet into very small pieces and then gluing them together into the desired cards is not allowed. Each card may be placed in either orientation (that is, it may be rotated by 90∘90^\circ).

An example of a 9×69 \times 6 paper sheet divided into 2×32 \times 3 cards is shown below.

Input

The first line contains the number of test cases tt (t≤105t \le 10^5). Each of the next tt lines contains four integers aa, bb, cc, dd (1≤a,b,c,d≤1091 \le a, b, c, d \le 10^9): a×ba \times b are the dimensions of each business card, and c×dc \times d are the dimensions of the paper sheet.

Output

For each test case, output a single line containing YES if the whole sheet can be divided into business cards, and NO otherwise.

Examples1

  1. Example 1

    Input
    4
2 3 9 6
2 3 8 6
2 3 6 8
2 3 5 7
    Expected output
    YES
YES
YES
NO