struct DSU
{
    vi p;
    DSU() {};
    DSU(int n)
    {
        p.resize(n);
        for (int i = 0; i < n; ++i)
            p[i] = i;
    }
    int get(int u)
    {
        if (u == p[u])
            return u;
        return p[u] = get(u);
    }
    void unit(int a, int b)
    {
        a = get(a);
        b = get(b);
        p[a] = b;
    }
};

map <int, int> cnt[100001];
vi G[100001];

int solve()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n - 1; ++i)
    {
        int x, y;
        scanf("%d %d", &x, &y);
        --x, --y;
        G[x].inb(y);
    }
    DSU T = DSU(n);
    function<void(int)> dfs = [&](int u)
    {
        if (G[u].size() == 1 && !G[G[u][0]].empty())
        {
            T.unit(u, G[u][0]);
        }
        for (int to : G[u])
        {
            dfs(to);
        }
    };
    dfs(0);
    int root = T.get(0);
    vi p(n, -1);
    function<void(int)> mkgraph = [&](int u)
    {
        for (int v : G[u])
        {
            int to = T.get(v);
            p[to] = u;
            mkgraph(to);
        }
    };
    mkgraph(root);
    for (int i = 0; i < n; ++i)
    {
        if (G[i].empty())
        {
            int it = 0;
            int x = T.get(i);
            int u = p[x];
            int cf = 1;
            while (u != -1 && cf < 1000000)
            {
                ++it;
                cf *= (int)G[u].size();
                cnt[u][cf]++;
                u = p[u];
            }
        }
    }
    int m;
    scanf("%d", &m);
    for (int it = 0; it < m; ++it)
    {
        int u, x;
        scanf("%d %d", &u, &x);
        int ans = x;
        --u;
        for (int i = 1; (int)i * i <= x; ++i)
        {
            if (x % i)
                continue;
            {
                int cd = i;
                if (cnt[u].find(cd) != cnt[u].end())
                    ans -= (x / cd) * cnt[u][cd];
            }
            if (x != i * i)
            {
                int cd = x / i;
                if (cnt[u].find(cd) != cnt[u].end())
                    ans -= (x / cd) * cnt[u][cd];
            }
        }
        printf("%d\n", max(ans, 0));
    }
    return 0;
}