<|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 \(t\) is a triangular number, i.e. there exists an integer \(k\ge 1\) with
   \[
   \frac{k(k+1)}{2} = t.
   \]
   A robust way is to compute an approximate \(k=\lfloor(-1+\sqrt{1+8t})/2\rfloor\) from the quadratic
   \(k^2+k-2t=0\), then adjust \(k\) up/down by a step to correct floating-point error, and finally test exact equality \(k(k+1)/2=t\).
4. If yes, output `"YES"`, else `"NO"`.

(Here \(k\) corresponds to \(n-1\), so \(k(k+1)/2=n(n-1)/2\) is the same condition.)

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

---

## 4) C++ implementation

```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int64_t m;

void read() { cin >> m; }

void solve() {
    // Let g(K) = #{ports in [K+1, 2K] with exactly 3 set bits}. The problem
    // gives us M = g(K) for some unknown K, and asks if K is uniquely
    // determined. We will prove that the answer is YES iff M >= 2 and (M-1) is
    // a triangular number. The key idea is to consider how g(K) changes as K
    // increases by 1. When K -> K+1, the interval [K+1, 2K] becomes [K+2,
    // 2K+2]. We lose port K + 1 and gain ports 2K + 1 and 2K + 2. So g(K + 1) -
    // g(K) = [popcount(2K+1)==3] + [popcount(2K+2)==3] - [popcount(K+1)==3].
    //
    // Note that 2K+2 = 2*(K+1), so popcount(2K+2) = popcount(K+1).
    // These cancel, giving g(K+1) - g(K) = [popcount(2K+1) == 3].
    // Since 2K+1 is odd, popcount(2K+1) = popcount(K) + 1.
    // So g(K+1) - g(K) = [popcount(K) == 2].
    //
    // Since g(1) = 0 (interval [2,2] has no 3-bit numbers), telescoping
    // gives:
    //
    //   g(K) = #{j in [1, K-1] : popcount(j) == 2}.
    //
    // This is a staircase function: g increases by 1 at each K where
    // popcount(K-1) = 2, and is constant between such points. So M = g(K)
    // determines K uniquely iff the step has width 1, i.e. both K-1 and K
    // have popcount 2 (g jumps at K, and also jumped at K-1).
    //
    // Two consecutive integers both have popcount 2 only around powers
    // of 2: the pairs are (2^n+1, 2^n+2) for n >= 2. At such a point,
    // g(2^n+2) = #{j in [1, 2^n+1] with popcount 2} = C(n,2) + 1
    // (choose 2 of the n low bits, plus 2^n+1 itself). We don't care about the
    // actual K - only whether some K exists. So just check: is M = C(n,2) + 1
    // for some n >= 2? Equivalently, is (M-1) a triangular number?

    if(m < 2) {
        cout << "NO\n";
        return;
    }

    int64_t t = m - 1;
    int64_t k = (int64_t)((-1.0 + sqrt(1.0 + 8.0 * t)) / 2.0);
    while(k * (k + 1) / 2 < t) {
        k++;
    }
    while(k > 0 && k * (k + 1) / 2 > t) {
        k--;
    }
    cout << (k > 0 && k * (k + 1) / 2 == t ? "YES\n" : "NO\n");
}

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

    int T = 1;
    cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    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\)).
