Rectangle matrices

4.5

10 votes
Algorithms, String Manipulation
Problem

You are given a rectangle matrix of size 1018×1018. The rows of the matrix are numbered 1 to 1018 from top to bottom and the columns of the matrix are numbered 1 to 1018 from left to right. The cell of the field at the intersection of the xth row and yth column is represented by (x,y)

A rabbit is standing at cell (1,1). The rabbit can move from a cell (x,y) to a cell (2×x,y) or (x,2×y) in a few seconds because of its good speed. Also, it can move to (x,yx) or (xy,y)

Note: The rabbit cannot move out of the bounds of the matrix.

You purchase food for the rabbit for the next q days. You place the food in the cell (xi,yi) on the ith day but you are unsure if these cells are reachable. Your task is to determine if you can reach from the cell (1,1) to the cell (xi,yi).

Input format

  • First line: Integer q denoting the number of days
  • Next q lines: Two space-separated integers xi and yi denoting the coordinates where the food is placed

Output format

For each of q days, print Yes in a single line if there is a path from cell (1,1) to cell (xi,yi) ensuring all the requirements are met. If it is not possible, print No.

Constraints

1q3×1051xi,yi1018

Sample Input
5
1 1
2 2
3 6
4 7
1000 1000
Sample Output
Yes
Yes
No
Yes
No
Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

-

Editor Image

?