<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

255. Winsock 3 Beta
time limit per test: 0.25 sec.
memory limit per test: 65536 KB
input: standard
output: standard



Recently one famous company "Macrohard" announced the new version of its well-known network API called WinSuck 3 Beta. Small company "Analogotron" where you work asks you to probe that radically new programming library for future usage in the new tele-broadcasting complex.
You entered the research stage three months ago and now you are completely depressed. Earlier you had worked with WinSock 2 and all seemed to be fine, but you absolutely can not understand the logic of data sending/receiving mechanism of the new library.
At the forum of software developers you learned that "Macrohard" implemented the low-level security system, so now when estabilishing connection it generates some positive integer K and uses it in the following way.
When you are sending data to ports in range from K+1 to 2K the firewall is not blocking it if there are exactly three non-zero bits in port number. Ports out of range are always blocked by the firewall. For proper usage of the library you need to know the security key K, so you send data to all available ports (in range from 0 to +infinity), and only M of them were not blocked.
Now you must find whether you can detect the number K exactly.

Input
The first line of input contains single integer N - the number of tests (0<=N<=100). The following N lines contain tests descriptions (one line per test). Test description contains single integer M (0<=M<=2^31-1).

Output
Output N lines (one line per test). Line should contain "YES" (without quotes) if you can exactly detect number K given such M, or "NO" (without quotes) in the other case.

Sample test(s)

Input
2
1
2

Output
NO
YES
Author:	Alexey Preobrajensky
Resource:	Petrozavodsk Summer Training Sessions 2004
Date:	August 25, 2004

<|response|>
## 1) Abridged problem statement (concise)

A secret positive integer \(K\) is chosen. Only ports \(p\) in the range \([K+1,\,2K]\) may pass the firewall, and among them a port passes **iff** its binary representation has **exactly 3 set bits**.

You test all ports and observe that exactly \(M\) ports pass.

For each given \(M\), decide whether this \(M\) determines \(K\) **uniquely**. Output:

- `"YES"` if there is **exactly one** \(K\) that could produce this \(M\)
- `"NO"` otherwise.

---

## 2) Key observations

Let

\[
g(K)=\#\{p\in[K+1,2K]\;:\;\text{popcount}(p)=3\}
\]

You are given \(M=g(K)\), want to know if \(K\) is uniquely determined by \(M\).

### Observation A: How \(g(K)\) changes when \(K\to K+1\)

Intervals:

- for \(K\): \([K+1,2K]\)
- for \(K+1\): \([K+2,2K+2]\)

So we **lose** \(K+1\), and **gain** \(2K+1\) and \(2K+2\):

\[
g(K+1)-g(K) = [pc(2K+1)=3] + [pc(2K+2)=3] - [pc(K+1)=3]
\]

But \(2K+2 = 2(K+1)\) is a left shift, so popcount is unchanged:

\[
pc(2K+2)=pc(K+1)
\]

They cancel:

\[
g(K+1)-g(K) = [pc(2K+1)=3]
\]

And \(2K+1\) is \(K\) shifted left plus a trailing 1, so:

\[
pc(2K+1)=pc(K)+1
\]

Thus:

\[
g(K+1)-g(K) = [pc(K)=2]
\]

**Meaning:** \(g(K)\) increases by 1 **exactly** at those \(K\) which have popcount 2.

---

### Observation B: Telescoping formula for \(g(K)\)

We have \(g(1)=0\) (interval \([2,2]\) has no 3-bit number).

So:

\[
g(K)=\sum_{i=1}^{K-1}(g(i+1)-g(i))=\#\{j\in[1,K-1]: pc(j)=2\}
\]

So \(M\) is the count of integers **below \(K\)** with exactly two set bits.

---

### Observation C: When does \(M\) uniquely determine \(K\)?

Since \(g(K)\) is non-decreasing and increases only at “special” \(K\), it forms a **staircase**. A value \(M\) uniquely determines \(K\) iff the plateau at height \(M\) has **length 1**.

That happens exactly when \(g\) increases at two consecutive steps, i.e. when **both** \(K-1\) and \(K\) have popcount 2.

Consecutive integers both with popcount 2 are only:

\[
2^n+1 \;\; \text{and}\;\; 2^n+2 \quad (n\ge 2)
\]

Therefore the unique \(K\) must be:

\[
K = 2^n+2
\]

---

### Observation D: What \(M\) values are “unique”?

Compute:

\[
M=g(2^n+2)=\#\{j\in[1,2^n+1]: pc(j)=2\}
\]

Count popcount-2 numbers \(\le 2^n+1\):

- Among numbers \(<2^n\): choose 2 bit positions among the lowest \(n\) bits  
  \(\binom{n}{2}\)
- Plus the number \(2^n+1\) itself (bits at positions \(n\) and 0): \(+1\)

So:

\[
M=\binom{n}{2}+1
\quad\Rightarrow\quad
M-1=\binom{n}{2}=\frac{n(n-1)}{2}
\]

So:

> **Answer is YES iff** \(M\ge 2\) and \(M-1\) is a triangular number.

---

## 3) Full solution approach

For each test case with value \(M\):

1. If \(M<2\), output `"NO"` (cannot be unique).
2. Let \(t=M-1\).
3. Check whether there exists an integer \(n\ge 2\) such that:
   \[
   \frac{n(n-1)}{2} = t
   \]
   Equivalently, solve \(n^2-n-2t=0\). The discriminant:
   \[
   D = 1 + 8t
   \]
   We need \(D\) to be a perfect square, and then:
   \[
   n = \frac{1+\sqrt{D}}{2}
   \]
   must be an integer \(\ge 2\).
4. If yes, output `"YES"`, else `"NO"`.

Complexity per test: \(O(1)\). Works easily for \(M\le 2^{31}-1\).

---

## 4) C++ implementation (detailed comments)

```cpp
#include <bits/stdc++.h>
using namespace std;

/*
We derived:
  answer = YES  <=>  M >= 2 and (M-1) is triangular:
      M-1 = n(n-1)/2 for some integer n >= 2

Checking triangularity:
  n(n-1)/2 = t
  => n^2 - n - 2t = 0
  Discriminant D = 1 + 8t must be perfect square.
  Then n = (1 + sqrt(D)) / 2 must be integer.
*/

static bool isPerfectSquare(long long x) {
    if (x < 0) return false;
    long long r = (long long)llround(floor(sqrt((long double)x)));
    while (r * r < x) ++r;
    while (r * r > x) --r;
    return r * r == x;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        long long M;
        cin >> M;

        if (M < 2) {                 // M=0 or 1 can never uniquely determine K
            cout << "NO\n";
            continue;
        }

        long long t = M - 1;         // Need t to be triangular of form n(n-1)/2
        long long D = 1 + 8 * t;     // discriminant

        if (!isPerfectSquare(D)) {   // sqrt(D) must be integer
            cout << "NO\n";
            continue;
        }

        long long s = (long long) llround(floor(sqrt((long double)D)));
        // n = (1 + s)/2 must be integer, i.e. (1+s) even
        if ( (1 + s) % 2 != 0 ) {
            cout << "NO\n";
            continue;
        }

        long long n = (1 + s) / 2;
        // Ensure n>=2 and exact equality (guards against any rounding issues)
        if (n >= 2 && n * (n - 1) / 2 == t) cout << "YES\n";
        else cout << "NO\n";
    }

    return 0;
}
```

---

## 5) Python implementation (detailed comments)

```python
import sys
import math

def is_unique(M: int) -> bool:
    """
    Derived criterion:
      YES <=> M >= 2 and (M-1) = n(n-1)/2 for some integer n >= 2.

    Use discriminant:
      n^2 - n - 2t = 0, where t = M-1
      D = 1 + 8t must be a perfect square,
      n = (1 + sqrt(D)) / 2 must be integer.
    """
    if M < 2:
        return False

    t = M - 1
    D = 1 + 8 * t

    s = math.isqrt(D)
    if s * s != D:
        return False

    # n = (1 + s)/2 must be integer
    if (1 + s) % 2 != 0:
        return False

    n = (1 + s) // 2
    return n >= 2 and n * (n - 1) // 2 == t


def main() -> None:
    data = sys.stdin.read().strip().split()
    if not data:
        return
    T = int(data[0])
    out = []
    for i in range(1, 1 + T):
        M = int(data[i])
        out.append("YES" if is_unique(M) else "NO")
    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()
```

This directly implements the proven characterization: **unique \(K\)** happens exactly when **\(M-1\)** is a triangular number (and \(M\ge 2\)).