using namespace std;
using ll = long long;
const int NMAX = 1e3 + 11;
const int MWMAX = 30 + 11;
int n, g;
int p[NMAX], w[NMAX], mem[NMAX][MWMAX];
int dp(int pos, int capacity)
{
    int &ans = mem[pos][capacity];
    if (pos == n)
        return 0;
    if (ans != -1)
        return ans;
    if (capacity - w[pos] >= 0)
        ans = dp(pos + 1, capacity - w[pos]) + p[pos];
    return (ans = max(ans, dp(pos + 1, capacity)));
}
int main(void)
{
    int t, mw;
    cin >> t;
    while (t--)
    {
        ll ans = 0;
        cin >> n;
        for (int i = 0; i < n; ++i)
            cin >> p[i] >> w[i];
        cin >> g;
        for (int i = 0; i < n; ++i)
            memset(mem[i], -1, MWMAX * sizeof(int));
        for (int i = 0; i < g; ++i)
        {
            cin >> mw;
            ans += dp(0, mw);
        }
        cout << ans << endl;
    }
    return 0;
}

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 vi = vector<int>;
const int NMAX = 2 * 1e5 + 11;
int n, k, depth[NMAX];
vi g[NMAX], ans;
int dfs(int u, int parent, int depth = 0)
{
    int children = 0;
    for (int v : g[u])
        if (v != parent)
            children += 1 + dfs(v, u, depth + 1);
    ans.push_back(depth - children);
    return children;
}
int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int u, v;
    cin >> n >> k;
    for (int i = 0; i < n - 1; ++i)
    {
        cin >> u >> v;
        g[u - 1].push_back(v - 1);
        g[v - 1].push_back(u - 1);
    }
    dfs(0, -1);
    sort(ans.rbegin(), ans.rend());
    cout << accumulate(ans.begin(), ans.begin() + k, 0LL) << endl;
    return 0;
}

const int NMAX = 1e5 + 10;
using namespace std;
using ll = long long;
ll n, a[NMAX], seg[4 * NMAX], lazy[4 * NMAX];
void build(ll a[], ll v, ll tl, ll tr)
{
    if (tl == tr)
        seg[v] = a[tl];
    else
    {
        ll tm = (tl + tr) / 2;
        build(a, v * 2, tl, tm);
        build(a, v * 2 + 1, tm + 1, tr);
        seg[v] = seg[2 * v] + seg[2 * v + 1];
    }
}
void lazy_propagate(ll v, ll tl, ll tr, ll val)
{
    seg[v] += (tr - tl + 1) * val;
    if (tl != tr)
    {
        lazy[2 * v] += val;
        lazy[2 * v + 1] += val;
    }
    lazy[v] = 0;
}
void update(ll v, ll tl, ll tr, ll ql, ll qr, ll x)
{
    if (lazy[v] != 0)
        lazy_propagate(v, tl, tr, lazy[v]);
    if (ql > qr)
        return;
    if (tl == ql and tr == qr)
        lazy_propagate(
            v, tl, tr, x);
    else
    {
        ll tm = (tl + tr) / 2;
        update(v * 2, tl, tm, ql, min(qr, tm), x);
        update(v * 2 + 1, tm + 1, tr, max(ql, tm + 1), qr, x);
        seg[v] = seg[2 * v] + seg[2 * v + 1];
    }
}
ll query(ll v, ll tl, ll tr, ll ql, ll qr)
{
    if (lazy[v] != 0)
        lazy_propagate(v, tl, tr, lazy[v]);
    if (ql > qr)
        return 0;
    if (tl == ql and tr == qr)
        return seg[v];
    else
    {
        ll tm = (tl + tr) / 2;
        return query(v * 2, tl, tm, ql, min(qr, tm)) +
               query(v * 2 + 1, tm + 1, tr, max(ql, tm + 1), qr);
    }
}
int main(void)
{
    ll t, q, type, l, r, x;
    cin >> t;
    while (t--)
    {
        cin >> n >> q;
        while (q--)
        {
            cin >> type >> l >> r;
            if (type)
                cout << query(1, 0, n - 1, l - 1, r - 1) << endl;
            else
            {
                cin >> x;
                update(1, 0, n - 1, l - 1, r - 1, x);
            }
        }
        memset(seg, 0, 4 * NMAX * sizeof(ll));
        memset(lazy, 0, 4 * NMAX * sizeof(ll));
        memset(a, 0, n * sizeof(ll));
    }
    return 0;
}

using namespace std;
const int NMAX = 50000 + 11;
struct node
{
    int ls, rs, ss, ts;
};
int n;
int a[NMAX];
node t[4 * NMAX];
node make_node(int x)
{
    node ans;
    ans.ts = x;
    ans.ls = ans.rs = ans.ss = max(0, x);
    return ans;
}
node combine(node lc, node rc)
{
    int ls, rs, ss, ts;
    ls = max(lc.ls, lc.ts + rc.ls);
    rs = max(rc.rs, rc.ts + lc.rs);
    ss = max({lc.ss, rc.ss, lc.rs + rc.ls});
    ts = lc.ts + rc.ts;
    return {ls, rs, ss, ts};
}
void update(int v, int tl, int tr, int pos, int new_val)
{
    if (tl == tr)
        t[v] = {new_val, new_val, new_val, new_val};
    else
    {
        int tm = (tl + tr) / 2;
        if (pos <= tm)
            update(v * 2, tl, tm, pos, new_val);
        else
            update(v * 2 + 1, tm + 1, tr, pos, new_val);
        t[v] = combine(t[v * 2], t[v * 2 + 1]);
    }
}
void build(int a[], int v, int tl, int tr)
{
    if (tl == tr)
        t[v] = {a[tl], a[tl], a[tl], a[tl]};
    else
    {
        int tm = (tl + tr) / 2;
        build(a, v * 2, tl, tm);
        build(a, v * 2 + 1, tm + 1, tr);
        t[v] = combine(t[v * 2], t[v * 2 + 1]);
    }
}
node query(int v, int tl, int tr, int l, int r)
{
    if (l > r)
        return make_node(0);
    if (l == tl and r == tr)
        return t[v];
    int tm = (tl + tr) / 2;
    if (r <= tm)
        return query(v * 2, tl, tm, l, r);
    if (l > tm)
        return query(v * 2 + 1, tm + 1, tr, l, r);
    return combine(query(v * 2, tl, tm, l, tm),
                   query(v * 2 + 1, tm + 1, tr, tm + 1, r));
}
int main(void)
{
    int m, l, r, type;
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    build(a, 1, 0, n - 1);
    cin >> m;
    while (m--)
    {
        cin >> type >> l >> r;
        if (type == 1)
            cout << query(1, 0, n - 1, l - 1, r - 1).ss << endl;
        else
            update(1, 0, n - 1, l - 1, r);
    }
    return 0;
}

using namespace std;
const int NMAX = 50000 + 11;
struct node
{
    int ls, rs, ss, ts;
};
int n;
int a[NMAX];
node t[4 * NMAX];
node make_node(int x)
{
    node ans;
    ans.ts = x;
    ans.ls = ans.rs = ans.ss = max(0, x);
    return ans;
}
node combine(node lc, node rc)
{
    int ls, rs, ss, ts;
    ls = max(lc.ls, lc.ts + rc.ls);
    rs = max(rc.rs, rc.ts + lc.rs);
    ss = max({lc.ss, rc.ss, lc.rs + rc.ls});
    ts = lc.ts + rc.ts;
    return {ls, rs, ss, ts};
}
void build(int a[], int v, int tl, int tr)
{
    if (tl == tr)
        t[v] = {a[tl], a[tl], a[tl], a[tl]};
    else
    {
        int tm = (tl + tr) / 2;
        build(a, v * 2, tl, tm);
        build(a, v * 2 + 1, tm + 1, tr);
        t[v] = combine(t[v * 2], t[v * 2 + 1]);
    }
}
node query(int v, int tl, int tr, int l, int r)
{
    if (l > r)
        return make_node(0);
    if (l == tl and r == tr)
        return t[v];
    int tm = (tl + tr) / 2;
    if (r <= tm)
        return query(v * 2, tl, tm, l, r);
    if (l > tm)
        return query(v * 2 + 1, tm + 1, tr, l, r);
    return combine(query(v * 2, tl, tm, l, tm),
                   query(v * 2 + 1, tm + 1, tr, tm + 1, r));
}
int main(void)
{
    int m, l, r;
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    build(a, 1, 0, n - 1);
    cin >> m;
    while (m--)
    {
        cin >> l >> r;
        cout << query(1, 0, n - 1, l - 1, r - 1).ss << endl;
    }
    return 0;
}