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

113. Nearly prime numbers

time limit per test: 0.25 sec.
memory limit per test: 4096 KB


Nearly prime number is an integer positive number for which it is possible to find such primes P1 and P2 that given number is equal to P1*P2. There is given a sequence on N integer positive numbers, you are to write a program that prints “Yes” if given number is nearly prime and “No” otherwise.


Input

Input file consists of N+1 numbers. First is positive integer N (1£N£10). Next N numbers followed by N. Each number is not greater than 109. All numbers separated by whitespace(s).


Output

Write a line in output file for each number of given sequence. Write “Yes” in it if given number is nearly prime and “No” in other case.


Sample Input

1
6
Sample Output

Yes
Author	: Michael R. Mirzayanov
Resource	: PhTL #1 Training Contests
Date	: Fall 2001

<|response|>
1. Abridged Problem Statement
Given N (1 ≤ N ≤ 10) positive integers (each ≤ 10^9), determine for each one whether it is the product of exactly two primes (primes need not be distinct). Print “Yes” if it is, otherwise “No.”

2. Key Observations
- A number X is “nearly prime” iff its prime-factorization has exactly two prime factors counted with multiplicity.
  • e.g. 6 = 2·3 → two prime factors → nearly prime
  • 9 = 3·3 → two prime factors (same prime twice) → nearly prime
  • 4 = 2·2 → nearly prime
  • 8 = 2·2·2 → three prime factors → not nearly prime
  • 1 has zero prime factors → not nearly prime
  • Any prime p has one prime factor → not nearly prime
- To count prime factors (with multiplicity) of X ≤ 10^9, trial-divide by all integers d from 2 up to √X.
- Maintain a counter c; every time d divides X, do c++ and X /= d.
- After the loop, if the remaining X > 1, that remaining piece is a prime factor → c++.
- Finally check if c == 2.

3. Full Solution Approach
For each input number A:
  1. Let x = A, c = 0.
  2. For d from 2 to floor(√x):
       while x % d == 0:
         c++;
         x /= d;
  3. If x > 1 after the loop, then x is prime → c++.
  4. If c == 2, print “Yes”; otherwise print “No.”
Complexity: each A costs O(√A) divisions. With N ≤ 10 and A ≤ 10^9, this runs comfortably within time limits.

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;
};

int n;
vector<int> a;

void read() {
    cin >> n;
    a.resize(n);
    cin >> a;
}

void solve() {
    // A nearly prime number is a product of exactly two primes. For each value
    // trial-divide out prime factors counting them with multiplicity; the
    // number is nearly prime iff the total count of prime factors is exactly 2.

    for(int i = 0; i < n; i++) {
        int x = a[i];
        int cnt = 0;
        for(int d = 2; d * 1ll * d <= x; d++) {
            while(x % d == 0) {
                cnt++;
                x /= d;
            }
        }

        if(x != 1) {
            cnt++;
        }

        cout << (cnt == 2 ? "Yes" : "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();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

5. Python Implementation with Detailed Comments
```python
import sys
import math

def is_nearly_prime(x):
    """
    Return True if x has exactly two prime factors (with multiplicity).
    """
    count = 0
    # trial divide by 2 first
    while x % 2 == 0:
        count += 1
        x //= 2
        if count > 2:
            return False

    # now try odd divisors
    d = 3
    # only need to go up to sqrt(x)
    while d * d <= x:
        while x % d == 0:
            count += 1
            x //= d
            if count > 2:
                return False
        d += 2

    # if remaining x > 1, it's a prime factor
    if x > 1:
        count += 1

    return (count == 2)

def main():
    data = sys.stdin.read().split()
    N = int(data[0])
    nums = map(int, data[1:])

    for x in nums:
        print("Yes" if is_nearly_prime(x) else "No")

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

Explanation of key parts:
- We count factors by repeated division.
- After trial division up to √x, any leftover x>1 must itself be prime, so contributes one more factor.
- Finally check if total count equals 2.
