Under construction

Still being built. Things may change

Multiplication and Division by 2

Interview

Time limit2sMemory limit512 MB

Summary
Given two uint32 values x and y, decide whether repeated multiplication by 2 mod 2^32 and floor division by 2 can turn x into y.
Level

Medium5 of 10

Topics
Bit manipulation, Math, Implementation, Brute force
Solved
No attempts yet

Problem

Consider the number xx stored in the uint32 data type. We can multiply or divide it by 22 any number of times in any order. Can we obtain the number yy after some sequence of operations?

When aa is stored in a uint32 and we multiply it by 22, it becomes (a⋅2) mod 232(a \cdot 2) \bmod 2^{32}. For example, (3⋅2) mod 232=6(3 \cdot 2) \bmod 2^{32} = 6, and (2 147 483 649⋅2) mod 232=2(2\,147\,483\,649 \cdot 2) \bmod 2^{32} = 2.

When aa is stored in a uint32 and we divide it by 22, it becomes ⌊a2⌋\left\lfloor\frac{a}{2}\right\rfloor. For example, ⌊62⌋=3\left\lfloor\frac{6}{2}\right\rfloor = 3, and ⌊32⌋=1\left\lfloor\frac{3}{2}\right\rfloor = 1.

Input

The first line contains an integer tt, the number of test cases (1≤t≤10001 \le t \le 1000). The next tt lines describe test cases, one per line. Each test case is given by two integers xx and yy (0≤x,y<2320 \le x, y < 2^{32}).

Output

For each test case, print a single word on a separate line: "Yes" if we can turn xx into yy using the allowed operations, or "No" otherwise.

Hint

In the first test case, we can multiply xx by 22, and then divide the result by 22 to get yy.

In the second test case, there is no way to turn xx into yy.

Examples1

  1. Example 1

    Input
    2
    2147483649 1
    9 13
    
    Expected output
    Yes
    No