using namespace std;
using ll = long long;
ll count_divisors(ll n)
{
    ll sqrtn = sqrt(n), ans = 0;
    for (ll i = 1; i <= sqrtn; ++i)
        if (n % i == 0)
            ans += 2;
    if (sqrtn * sqrtn == n)
        --ans;
    return ans;
}
int main(void)
{
    ll n;
    string ans[2] = {"no", "yes"};
    while (cin >> n and n != 0)
        cout << ans[count_divisors(n) % 2] << endl;
    return 0;
}

using namespace std;
using vi = vector<int>;
const int NMAX = 10e4;
struct state
{
    int a[4];
    int depth;
    state(vi v) { copy(v.begin(), v.end(), a); }
    state(void) {}
    int index(void) const
    {
        int ans = 0, pten = 1;
        for (int i = 0; i < 4; ++i)
        {
            ans += a[i] * pten;
            pten *= 10;
        }
        return ans;
    }
    void cin_init(void)
    {
        for (int i = 0; i < 4; ++i)
            cin >> a[i];
    }
    bool operator==(const state &s2) const
    {
        for (int i = 0; i < 4; ++i)
        {
            if (a[i] != s2.a[i])
                return false;
        }
        return true;
    }
};
bool visited[NMAX] = {false};
int moves[8][4] = {{1, 0, 0, 0},
                   {-1, 0, 0, 0},
                   {0, 1, 0, 0},
                   {0, -1, 0, 0},
                   {0, 0, 1, 0},
                   {0, 0, -1, 0},
                   {0, 0, 0, 1},
                   {0, 0, 0, -1}};
int mod(int x) { return ((x % 10) + 10) % 10; }
vector<state> next_states(state s)
{
    state ans[8];
    for (int i = 0; i < 8; ++i)
    {
        ans[i].depth = s.depth + 1;
        for (int j = 0; j < 4; ++j)
            ans[i].a[j] = mod(s.a[j] + moves[i][j]);
    }
    return vector<state>(ans, ans + 8);
}
int bfs(state start, state target)
{
    state current;
    queue<state> q;
    if (visited[start.index()])
        return -1;
    q.push(start);
    while (not q.empty())
    {
        current = q.front();
        q.pop();
        if (current == target)
            return current.depth;
        for (state next : next_states(current))
        {
            if (not visited[next.index()])
            {
                visited[next.index()] = true;
                q.push(next);
            }
        }
    }
    return -1;
}
int main(void)
{
    int t, n;
    state start, target, forbidden;
    cin >> t;
    while (t--)
    {
        memset(visited, false, NMAX);
        start.cin_init();
        target.cin_init();
        cin >> n;
        while (n--)
        {
            forbidden.cin_init();
            visited[forbidden.index()] = true;
        }
        start.depth = 0;
        cout << bfs(start, target) << endl;
    }
    return 0;
}

using namespace std;
using ii = pair<int, int>;
using mii = map<int, int, greater<int>>;
int const INF = 2e9;
int solve(int x, mii &a)
{
    int cnt = 0, ccnt;
    auto begin = a.begin();
    while (x > 0)
    {
        auto it = lower_bound(begin, a.end(), make_pair(x, INF), greater<ii>());
        if (it == a.end())
            return -1;
        ccnt = min(it->second, x / it->first);
        x -= it->first * ccnt;
        begin = next(it);
        cnt += ccnt;
    }
    return cnt;
}
int main(void)
{
    int n, q, x;
    mii a;
    cin >> n >> q;
    for (int i = 0; i < n; ++i)
    {
        int ai;
        cin >> ai;
        a[ai]++;
    }
    while (q--)
    {
        cin >> x;
        cout << solve(x, a) << endl;
    }
    return 0;
}

using namespace std;
using ll = long long;
using predicate = function<bool(ll)>;
using vll = vector<ll>;
ll n, p, q;
vll a;
ll binary_search(ll lo, ll hi, predicate p)
{
    while (lo < hi)
    {
        ll mid = lo + (hi - lo) / 2;
        if (p(mid) == true)
            hi = mid;
        else
            lo = mid + 1;
    }
    if (p(lo) == false)
        return -1;
    return lo;
}
bool hits_suffice(ll x)
{
    ll total_hits;
    if (p == q)
        total_hits = (*max_element(a.begin(), a.end()) + p - 1) / p;
    else
        total_hits =
            accumulate(a.begin(), a.end(), (ll)0, [x](ll acc, ll ai) -> ll {
                ll ai_prime = ai - x * q;
                ll p_prime = p - q;
                return acc + max((ll)0, (ai_prime + p_prime - 1) / p_prime);
            });
    return x >= total_hits;
}
int main(void)
{
    cin >> n >> p >> q;
    a = vll(n);
    for (auto &x : a)
        cin >> x;
    cout << binary_search(0, 1e9 + 11, hits_suffice) << endl;
    return 0;
}

using namespace std;
using ll = long long;
const int NMAX = 1e7;
bitset<NMAX> is_prime;
vector<int> primes;
void sieve(ll n)
{
    is_prime.set();
    is_prime[0] = is_prime[1] = 0;
    for (ll i = 2; i <= n; ++i)
    {
        if (is_prime[i])
        {
            primes.push_back(i);
            for (ll j = i * i; j <= n; j += i)
                is_prime[j] = 0;
        }
    }
}
bool is_prime_util(ll n)
{
    if (n < NMAX)
        return is_prime[n];
    for (int i = 0; i < (int)primes.size() and (ll)(primes[i] * primes[i]) <= n;
         ++i)
        if (n % primes[i])
            return false;
    return true;
}
int mod_exp(int base, int exp, int mod)
{
    ll ans;
    if (base == 0)
        return 0;
    if (exp == 0)
        return 1;
    if (exp % 2 == 0)
    {
        ans = mod_exp(base, exp / 2, mod);
        ans = (ans * ans) % mod;
    }
    else
    {
        ans = base % mod;
        ans = (ans * mod_exp(base, exp - 1, mod) % mod) % mod;
    }
    return (int)ans;
}
bool is_carmichael(int n)
{
    for (int a = 2; a <= n - 1; ++a)
    {
        if (mod_exp(a, n, n) != a)
            return false;
    }
    return true;
}
int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    sieve(NMAX);
    while (cin >> n and n)
    {
        if (not is_prime_util(n) and is_carmichael(n))
            cout << "The number " << n << " is a Carmichael number." << endl;
        else
            cout << n << " is normal." << endl;
    }
}

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
using mint = atcoder::modint1000000007;
struct LCA
{
    using vi = vector<int>;
    using Tree = vector<vi>;
    int n;
    vector<vi> up;
    vi tin, tout;
    LCA(const Tree &g) : n(g.size()), up(n, vi(log2(n) + 2)), tin(n), tout(n)
    {
        int timer = 0;
        preprocess(g, 0, 0, timer);
    }
    void preprocess(const Tree &g, int u, int p, int &timer)
    {
        tin[u] = ++timer;
        up[u][0] = p;
        for (int i = 1, height = up[0].size(); i < height; ++i)
            up[u][i] = up[up[u][i - 1]][i - 1];
        for (int v : g[u])
            if (v != p)
                preprocess(g, v, u, timer);
        tout[u] = ++timer;
    }
    bool is_ancestor(int u, int v) const
    {
        return tin[u] <= tin[v] and tout[u] >= tout[v];
    }
    int ancestor(int u, int k) const
    {
        int i;
        while (k)
        {
            i = 8 * sizeof(k) - __builtin_clz(k) - 1;
            u = up[u][i];
            k ^= 1LL << i;
        }
        if (u == 0)
            return -1;
        return u;
    }
    int lca(int u, int v) const
    {
        if (is_ancestor(u, v))
            return u;
        if (is_ancestor(v, u))
            return v;
        for (int i = up[0].size() - 1; i >= 0; --i)
            if (!is_ancestor(up[u][i], v))
                u = up[u][i];
        return up[u][0];
    }
    int operator()(int u, int v) const { return lca(u, v); }
};
template <typename T>
using Graph = vector<vector<T>>;
tuple<Graph<int>, vector<int>, vector<bool>> compress_graph(Graph<int> g,
                                                            vector<ii> edges)
{
    using DSU = atcoder::dsu;
    int n = g.size();
    DSU dsu(n);
    vi parent(n), color(n, 0);
    function<void(int, int)> dfs = [&](int u, int p) {
        color[u] = 1;
        parent[u] = p;
        for (auto v : g[u])
        {
            if (v == p)
                continue;
            if (color[v] == 1)
                for (int i = u; i != parent[v]; i = parent[i])
                    dsu.merge(v, i);
            else if (color[v] == 0)
                dfs(v, u);
        }
        color[u] = 2;
    };
    dfs(0, 0);
    auto components = dsu.groups();
    int nc = components.size();
    Graph<int> gc(nc);
    vector<int> id(n);
    vector<bool> in_cycle(nc, false);
    for (int i = 0; i < nc; ++i)
    {
        if (components[i].size() > 1)
            in_cycle[i] = true;
        for (auto u : components[i])
            id[u] = i;
    }
    transform(begin(edges), end(edges), begin(edges), [&id](ii uv) {
        return ii{id[uv.first], id[uv.second]};
    });
    edges.erase(
        remove_if(begin(edges), end(edges), [](ii uv) { return uv.first == uv.second; }),
        edges.end());
    sort(begin(edges), end(edges));
    edges.resize(distance(edges.begin(), unique(begin(edges), end(edges))));
    for (auto [u, v] : edges)
        gc[u].push_back(v), gc[v].push_back(u);
    return {gc, id, in_cycle};
}
vector<int> compute_dp(const Graph<int> g, vector<bool> black)
{
    vector<int> dp(begin(black), end(black));
    function<void(int, int)> dfs = [&](int u, int p) {
        for (auto v : g[u])
        {
            if (v == p)
                continue;
            dp[v] += dp[u];
            dfs(v, u);
        }
    };
    dfs(0, 0);
    return dp;
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    Graph<int> g(n);
    vector<ii> edges(m);
    for (int i = 0; i < m; ++i)
    {
        int u, v;
        cin >> u >> v, u--, v--;
        g[u].push_back(v);
        g[v].push_back(u);
        edges[i] = {u, v};
    }
    auto [gc, id, black] = compress_graph(g, edges);
    auto dp = compute_dp(gc, black);
    LCA lca(gc);
    int k;
    cin >> k;
    while (k--)
    {
        int u, v;
        cin >> u >> v, u--, v--;
        u = id[u], v = id[v];
        int l = lca(u, v);
        int cnt = dp[u] + dp[v] - 2 * dp[l] + black[l];
        auto ans = mint(2).pow(cnt).val();
        cout << ans << endl;
    }
    return 0;
}

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
template <typename T>
T ceil(T a, T b)
{
    return a / b + (((a ^ b) >= 0) && (abs(a) % abs(b) != 0));
}
template <typename T>
struct DifferenceArray
{
    vector<T> d;
    array<ll, 2> unsigned_sum;
    DifferenceArray(const vector<T> &a) : d(a.size()), unsigned_sum({0, 0})
    {
        adjacent_difference(begin(a), end(a), begin(d));
        for (auto di : d)
            unsigned_sum[di > 0] += abs(di);
        unsigned_sum[d[0] > 0] -= abs(d[0]);
    }
    void update(int i, T x)
    {
        if (i >= (int)(d).size())
            return;
        if (i > 0)
            unsigned_sum[d[i] > 0] -= abs(d[i]);
        d[i] += x;
        if (i > 0)
            unsigned_sum[d[i] > 0] += abs(d[i]);
    }
    void update(int l, int r, T x) { update(l, +x), update(r + 1, -x); }
    vector<T> A() const
    {
        vector<T> ans(d.size());
        partial_sum(begin(d), end(d), begin(ans));
        return ans;
    }
    ll query() { return ceil(d[0] + unsigned_sum[1], 2LL); }
};
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n;
    cin >> n;
    vector<ll> a(n);
    for (auto &ai : a)
        cin >> ai;
    DifferenceArray da(a);
    cout << da.query() << endl;
    ((void)0);
    int q;
    cin >> q;
    while (q--)
    {
        int l, r, x;
        cin >> l >> r >> x, l--, r--;
        da.update(l, r, x);
        cout << da.query() << endl;
    }
    return 0;
}

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
template <typename T>
using Tree = vector<vector<T>>;
bool solve(Tree<int> g, int x)
{
    int n = g.size();
    vector<int> deg(n, 0);
    function<void(int, int)> dfs = [&](int u, int p) {
        for (auto v : g[u])
        {
            deg[u]++;
            if (v != p)
                dfs(v, u);
        }
    };
    dfs(x, -1);
    if (deg[x] <= 1)
        return 1;
    return ((n - 3) % 2) == 1;
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int t;
    cin >> t;
    string ans[2] = {"Ashish", "Ayush"};
    while (t--)
    {
        int n, x;
        cin >> n >> x, x--;
        Tree<int> g(n);
        for (int i = 0; i < n - 1; ++i)
        {
            int u, v;
            cin >> u >> v, u--, v--;
            g[u].push_back(v);
            g[v].push_back(u);
        }
        cout << ans[solve(g, x)] << endl;
    }
    return 0;
}

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
template <typename T, int N, int M>
struct Matrix
{
    using allocator_type = array<array<T, M>, N>;
    using self = Matrix<T, N, M>;
    allocator_type A;
    template <int R>
    Matrix<T, N, R> operator*(const Matrix<T, M, R> &B) const
    {
        Matrix<T, N, R> C;
        for (int i = 0; i < N; ++i)
            fill(begin(C[i]), end(C[i]), 0);
        for (int i = 0; i < N; ++i)
            for (int j = 0; j < R; ++j)
                for (int k = 0; k < M; ++k)
                    C[i][j] += A[i][k] * B[k][j];
        return C;
    }
    Matrix<T, N, M> operator+(const Matrix<T, N, M> &B)
    {
        Matrix<T, N, M> C;
        for (int i = 0; i < N; ++i)
            for (int j = 0; j < M; ++j)
                C[i][j] = A[i][j] + B[i][j];
    }
    template <typename V>
    Matrix<T, N, M> pow(V x) const
    {
        return *this;
    }
    array<T, M> &operator[](int i)
    {
        assert(0 <= i and i < N);
        return A[i];
    }
    const array<T, M> &operator[](int i) const
    {
        assert(0 <= i and i < N);
        return A[i];
    }
    Matrix<T, N, M> &operator=(array<array<T, N>, M> B)
    {
        A = B;
        return *this;
    }
};
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n;
    cin >> n;
    vector<Matrix<ll, 3, 1>> X(n);
    for (auto &x : X)
        cin >> x[0][0] >> x[1][0], x[2][0] = 1;
    int m;
    cin >> m;
    vector<Matrix<ll, 3, 3>> A(m + 1);
    A[0] = {{{{1, 0, 0}, {0, 1, 0}, {0, 0, 1}}}};
    for (int i = 1; i <= m; ++i)
    {
        int type;
        cin >> type;
        A[i] = [](int type) -> Matrix<ll, 3, 3> {
            int p;
            switch (type)
            {
            case 1:
                return {{{{0, 1, 0}, {-1, 0, 0}, {0, 0, 1}}}};
            case 2:
                return {{{{0, -1, 0}, {1, 0, 0}, {0, 0, 1}}}};
            case 3:
                cin >> p;
                return {{{{-1, 0, 2 * p}, {0, 1, 0}, {0, 0, 1}}}};
            case 4:
                cin >> p;
                return {{{{1, 0, 0}, {0, -1, 2 * p}, {0, 0, 1}}}};
            default:
                return {};
            }
        }(type)*A[i - 1];
    }
    int q;
    cin >> q;
    while (q--)
    {
        int a, b;
        cin >> a >> b, b--;
        auto ans = A[a] * X[b];
        cout << ans[0][0] << " " << ans[1][0] << endl;
    }
    return 0;
}

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
int solve(vi a)
{
    int const AMAX = *max_element(begin(a), end(a)) + 1, n = a.size();
    vi dp(AMAX, 0), cnt(AMAX, 0);
    for (auto ai : a)
        cnt[ai]++;
    for (int x = 1; x < AMAX; ++x)
    {
        dp[x] += cnt[x];
        for (int y = 2 * x; y < AMAX; y += x)
            dp[y] = max(dp[y], dp[x]);
    }
    return n - *max_element(begin(dp), end(dp));
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        vi a(n);
        for (auto &ai : a)
            cin >> ai;
        cout << solve(a) << endl;
    }
    return 0;
}