The first condition for a 400 number is equivalent to that \(N\) is a square number.

Since there are only \(10^6\) square numbers not greater than \(10^{12}\), so we will check each of them whether it is a 400 number to enumerate 400 numbers.

Since the set of prime factors of \(k\) and that of \(k^2\) are equal, it is sufficient to count the number of distinct prime factors of \(k = 1, 2, \ldots, 10^6\) to enumerate all 400 numbers.

The number of distinct prime factors of \(k = 1, 2, \ldots, 10^6\) can be found in the same manner as Eratosthenes’ sieve. Specifically, initialize a sequence \(V = (V_1, V_2, \ldots, V_{10^6})\) with \(0\), and for each prime \(p\) not greater than \(10^6\), add \(1\) to \(V_i\) for every \(i\) that is a multiple of \(p\). Then the final \(V_i\) is the number of distinct prime factors of \(i\).

Once we enumerate all the 400 numbers not greater than \(10^{12}\), one can perform a binary search against the sorted list of the 400 numbers to find the maximum 400 number less than or equal to \(A\).

By the way, the number of 400 numbers less than or equal to \(10^{12}\) is \(288726\). (To be confident about the execution time limit, it is sufficient to be aware that it is below \(10^6\).)

Sample code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
	int A = 1000001;
	vector<int> v(A);
	for (int i = 2; i < A; i++) {
		if (v[i] == 0) for (int j = i; j < A; j += i) v[j]++;
	}
	vector<ll> vec;
	for (ll i = 2; i < A; i++) if (v[i] == 2) vec.push_back(i * i);
	int q;
	cin >> q;
	while (q--) {
		ll a;
		cin >> a;
		cout << *prev(upper_bound(vec.begin(), vec.end(), a)) << '\n';
	}
}