You are to answer $T$ queries. For each query, you are given two positive integers $n$ and $m$. Determine whether it is possible to construct a sequence of positive integers $a_1, a_2, \dots, a_n$ such that there exists $1 \le j \le n$ with $a_j = m$, and there exists a non-negative integer $t$ satisfying $$\prod_{i=1}^{n} (a_i + a_{i+1}) = 2^{2^{t+1}}$$ where $a_{n+1} = a_1$.

If such a construction is possible, output YES; otherwise, output NO.

Input

The input is read from standard input. The first line contains a positive integer $T$ ($1 \le T \le 10^6$), representing the number of queries. Each of the next $T$ lines contains two positive integers $n$ and $m$ ($1 \le n \le 2 \times 10^6$, $1 \le m \le 2^{62} - 1$), representing the required length of the sequence and the value that must be present in the sequence.

Output

Output to standard output. For each query, output a single line containing the string YES or NO, indicating whether such a construction is possible.

Examples

Input 1

2
3 3
2 1

Output 1

YES
NO

Note 1

For the first query, by choosing $a_1 = 1, a_2 = 3, a_3 = 1$, we have $(1 + 3) \times (3 + 1) \times (1 + 1) = 32 = 2^5$, which satisfies the condition. For the second query, it can be shown that $(a_1 + a_2)^2 = 2^{2^{t+1}}$ has no positive integer solutions.