Subtask ~1~: Ta chứng minh đáp án không quá ~4 \times 10^6~. Thật vậy, giả sử ~x > 4 \times 10^6~ thì ~x^2 > 16 \times 10^{12}~. Vậy ~x~ và ~x^2~ sẽ có tổng cộng ~21~ chữ số. Nhưng chỉ có ~10~ chữ số khác nhau nên theo nguyên lí dirichlet, sẽ có ít nhất một chữ số xuất hiện lớn hơn hoặc ~3~ lần.

Do vậy ta chỉ cần duyệt đến ~4 \times 10^6~ và in ra đáp án nếu thoả mãn.

Subtask ~2~: Ta sắp xếp các số theo thứ tự ~n~ tăng dần. Lúc này đáp án của các truy vấn cũng tăng dần. Do đó ta có thể sử dụng kĩ thuật hai con trỏ để duy trì đáp án.

Cách khác là ta có thể sinh ra hết tất cả các số ~x~ thoả mãn điều kiện ~x~ và ~x^2~ có các chữ số xuất hiện tối đa ~2~ lần. Sau đó ta chặt nhị phân với mỗi ~n~.

Code mẫu

#include <bits/stdc++.h> // QioCas

#ifdef LOCAL
    #include </home/cas/Cp/Lib/debug.h>
#else
    #define console(...) void(202398)
#endif

using namespace std;
using ll = long long;

int n;
vector<int> points;

int cnt[10];
bool check(int n) {
    ll s = 1LL * n * n;
    for(int i = 0; i < 10; ++i) cnt[i] = 0;
    for(; s; s /= 10) cnt[s % 10]++;
    for(; n; n /= 10) cnt[n % 10]++;
    for(int i = 0; i < 10; ++i)
        if(cnt[i] > 2) return false;
    return true;
}

int main() {
    cin.tie(NULL)->sync_with_stdio(false);
    for(int i = 1; true ; ++i) {
        if(check(i))
            points.push_back(i);
        if(points.size() && points.back() == 3143168)
            break;
    }

    int t; cin >> t;
    while(t--) {
        cin >> n;
        if(n > points.back()) cout << -1 << "\n";
        else cout << *lower_bound(points.begin(), points.end(), n) << "\n";
    }

    return 0;
}