PROBLEM LINK:
Setter: Misha Chorniy
Tester: Hasan Jaddouh
Editorialist: Taranpreet Singh
DIFFICULTY:
Easy
PREREQUISITES:
Prime Sieve, or even Square root factorization would suffix, Pre-computation. Number-theory (optional).
PROBLEM:
Answer the queries of form, Given a number N, can this number be represented as sum of two semi-primes. Semi-prime is a product of any two distinct prime numbers.
SUPER QUICK EXPLANATION
- Pre-compute all primes up to MXN (MAX possible value of N) (or MXN/2 will also suffice). Calculate all Semi-primes by iterating over all pair of distinct primes.
- Now, calculate all possible sums which can be represented as sum of two semi-primes, by taking each pair of semi-prime.
- Answer queries in O(1) time using pre-computed values.
EXPLANATION
For this problem, I am explaining two solutions, Common approach as used by Setter and Tester as well as most teams. The other one is quite an overkill, strange way to solve this problem, used by editorialist only. 
Setter/Tester Approach
Calculate all the primes in range [2,MXN]. This can be done using Sieve of Eratosthenes or we can just naively check each number whether it is a prime or not.
For those unaware of Sieve of Eratosthenes, Enter the secret box.
Click to view
We create an array and initially, mark all numbers above 1 as prime. Then, we select number marked as prime which is not yet visited. For this prime, mark all its multiples as composite. We repeat this process until there are no prime left which are not visited yet. After this, only numbers not marked as composite are prime.
Now that we have the list of primes in an array, say pr. Now, we need to find the list fo semi-primes. we can iterate over all pairs of Distinct primes take their product and the values in range [1, MXN] are marked as semi-prime. So, now we have the list of semi-primes in range$[1, MXN]$.
Now, Computing final answer is just doing once again, Iterating over all pairs of semi-primes and if their sum is in range [1, MXN], mark the sum as reachable.
Answering queries become simple, as we just need to print whether the sum N is marked reachable or not.
Editorialist’s Approach (Not recommended at all 
)
This solution differs from above solution at the computation of list of semi-primes. Give a try to compute list of semi-primes without computing primes. It relies on the formula of Number of factors of a number.
The observation is, that all semi-primes have exactly four factors. (can also be proved eaisly) But, all numbers having four factors are of two types. Both semi-primes and perfect cubes will always have 4 factors. So, we iterate over all numbers, check if it has exactly four factors (including trivial factors) and is not perfect cube. If any number satisfy both criteria, it is marked as semi-prime.
After that, this solution is same as Author/Tester solution.
Time Complexity
Both Solutions have pre-computation time O(MXN^2) for iterating over all pairs of semi-primes, which dominates everything.
For a fact, Sieve of Eratosthenes takes O(N*log(logN)) time while Square root factorization takes O(N*\sqrt{N}) time.
Queries are answered in O(1) time, taking overall O(T) time.
SO, overall complexity is O(MXN^2).
AUTHOR’S AND TESTER’S SOLUTIONS:
Setter’s solution
Tester’s solution
Editorialist’s solution
Feel free to Share your approach, If it differs. Suggestions are always welcomed. 