OIG XIV - lic

// https://szkopul.edu.pl/problemset/problem/eqMHKut-ZAURUhO6-eIEUQS7/site/?key=statement

#include <algorithm>
#include <iostream>
#include <vector>

std::vector<long long> v;

int digitSum(long long a) {
    if (a == 0)
        return 0;
    else
        return (a % 10) + digitSum(a / 10);
}

void generate(const int up_limit = 3 * 1000 * 1000) {
    v.push_back(1);
    while (v.size() <= (size_t)up_limit) {
        const auto& last = v[v.size() - 1];
        const auto& digit_sum = digitSum(last);

        v.push_back(last + digit_sum * digit_sum);
    }
}

int main() {
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);

    generate();

    int t;
    std::cin >> t;

    for (; t > 0; t--) {
        long long a;
        std::cin >> a;

        int p = 0, k = v.size() - 1;
        while (p < k) {
            int s = (p + k + 1) / 2;

            if (v[s] <= a) {
                p = s;
            } else {
                k = s - 1;
            }
        }

        if (v[p] == a) {
            std::cout << "TAK\n";
        } else {
            std::cout << "NIE\n";
        }
    }

    return 0;
}