You are given a tree consisting of n vertices. Recall that a tree is an undirected connected acyclic graph. The given tree is rooted at the vertex 1.

You have to process q queries. In each query, you are given a vertex of the tree v and an integer k.

To process a query, you may delete any vertices from the tree in any order, except for the root and the vertex v. When a vertex is deleted, its children become the children of its parent. You have to process a query in such a way that maximizes the value of c(v) - m ⋅ k (where c(v) is the resulting number of children of the vertex v, and m is the number of vertices you have deleted). Print the maximum possible value you can obtain.

The queries are independent: the changes you make to the tree while processing a query don't affect the tree in other queries.

Input

The first line contains one integer n (1 ≤ n ≤ 2 ⋅ 10^5) — the number of vertices in the tree.

Then n-1 lines follow, the i-th of them contains two integers x_i and y_i (1 ≤ x_i, y_i ≤ n; x_i ≠ y_i) — the endpoints of the i-th edge. These edges form a tree.

The next line contains one integer q (1 ≤ q ≤ 2 ⋅ 10^5) — the number of queries.

Then q lines follow, the j-th of them contains two integers v_j and k_j (1 ≤ v_j ≤ n; 0 ≤ k_j ≤ 2 ⋅ 10^5) — the parameters of the j-th query.

Output

For each query, print one integer — the maximum value of c(v) - m ⋅ k you can achieve.

Example

Input


8
6 7
3 2
8 3
5 7
7 4
7 1
7 3
6
1 0
1 2
1 3
7 1
5 0
7 200000


Output


5
2
1
4
0
4

Note

The tree in the first example is shown in the following picture:

<image>

Answers to the queries are obtained as follows:

  1. v=1,k=0: you can delete vertices 7 and 3, so the vertex 1 has 5 children (vertices 2, 4, 5, 6, and 8), and the score is 5 - 2 ⋅ 0 = 5; 
  2. v=1,k=2: you can delete the vertex 7, so the vertex 1 has 4 children (vertices 3, 4, 5, and 6), and the score is 4 - 1 ⋅ 2 = 2. 
  3. v=1,k=3: you shouldn't delete any vertices, so the vertex 1 has only one child (vertex 7), and the score is 1 - 0 ⋅ 3 = 1; 
  4. v=7,k=1: you can delete the vertex 3, so the vertex 7 has 5 children (vertices 2, 4, 5, 6, and 8), and the score is 5 - 1 ⋅ 1 = 4; 
  5. v=5,k=0: no matter what you do, the vertex 5 will have no children, so the score is 0; 
  6. v=7,k=200000: you shouldn't delete any vertices, so the vertex 7 has 4 children (vertices 3, 4, 5, and 6), and the score is 4 - 0 ⋅ 200000 = 4. 
#include <bits/stdc++.h>
unsigned int Z;
void srand_() {
  struct timeval tv;
  gettimeofday(&tv, NULL);
  Z = tv.tv_sec ^ tv.tv_usec | 1;
}
int rand_() { return (Z *= 3) >> 1; }
void append(int **ej, int *eo, int i, int j) {
  int o = eo[i]++;
  if (o >= 2 && (o & o - 1) == 0)
    ej[i] = (int *)realloc(ej[i], o * 2 * sizeof *ej[i]);
  ej[i][o] = j;
}
int zz[1 + 200000], ll[1 + 200000], rr[1 + 200000], xx[1 + 200000],
    yy[1 + 200000], xx_[1 + 200000], yy_[1 + 200000], u_, l_, r_;
int node(int x, int y) {
  static int _ = 1;
  zz[_] = rand_();
  xx_[_] = xx[_] = x, yy_[_] = yy[_] = y;
  return _++;
}
void pul(int u) {
  int l = ll[u], r = rr[u];
  xx_[u] = xx[u] + xx_[l] + xx_[r], yy_[u] = yy[u] + yy_[l] + yy_[r];
}
long long cross(int x1, int y1, int x2, int y2) {
  return (long long)x1 * y2 - (long long)x2 * y1;
}
void split(int u, int x, int y) {
  long long c;
  if (u == 0) {
    u_ = l_ = r_ = 0;
    return;
  }
  c = cross(xx[u], yy[u], x, y);
  if (c < 0) {
    split(rr[u], x, y);
    rr[u] = l_, l_ = u;
  } else if (c > 0) {
    split(ll[u], x, y);
    ll[u] = r_, r_ = u;
  } else {
    u_ = u, l_ = ll[u], r_ = rr[u];
    ll[u] = rr[u] = 0;
  }
  pul(u);
}
int merge(int u, int v) {
  if (u == 0) return v;
  if (v == 0) return u;
  if (zz[u] < zz[v]) {
    rr[u] = merge(rr[u], v), pul(u);
    return u;
  } else {
    ll[v] = merge(u, ll[v]), pul(v);
    return v;
  }
}
int tr_add(int u, int v) {
  split(u, xx[v], yy[v]);
  xx[v] += xx[u_], yy[v] += yy[u_], pul(v);
  return merge(merge(l_, v), r_);
}
int tr_merge(int u, int v) {
  if (v) {
    u = tr_merge(u, ll[v]), u = tr_merge(u, rr[v]);
    ll[v] = rr[v] = 0, u = tr_add(u, v);
  }
  return u;
}
int tr_first(int u) { return ll[u] == 0 ? u : tr_first(ll[u]); }
int tr_remove_first(int u) {
  if (ll[u] == 0) return rr[u];
  ll[u] = tr_remove_first(ll[u]), pul(u);
  return u;
}
int tr_add_(int u, int x, int y) {
  while (u) {
    int v = tr_first(u);
    if (cross(x, y, xx[v], yy[v]) >= 0)
      x += xx[v], y += yy[v], u = tr_remove_first(u);
    else
      break;
  }
  return tr_add(u, node(x, y));
}
int tr_query(int u, int c) {
  int x = 0, y = 0;
  while (u)
    if (yy[u] - (long long)xx[u] * c > 0)
      x += xx_[ll[u]] + xx[u], y += yy_[ll[u]] + yy[u], u = rr[u];
    else
      u = ll[u];
  return y - x * c;
}
int *ej[200000], eo[200000], *eh[200000], eo_[200000], cc[200000], ans[200000],
    tt[200000], sz[200000];
void dfs(int p, int i) {
  int o, j_, t, y;
  sz[i] = 1, j_ = -1;
  for (o = eo[i]; o--;) {
    int j = ej[i][o];
    if (j != p) {
      dfs(i, j);
      if (j_ == -1 || sz[j_] < sz[j]) j_ = j;
      sz[i] += sz[j];
    }
  }
  t = tt[j_];
  for (o = eo[i]; o--;) {
    int j = ej[i][o];
    if (j != j_) t = tr_merge(t, tt[j]);
  }
  y = eo[i] - (p == -1 ? 0 : 1);
  for (o = eo_[i]; o--;) {
    int h = eh[i][o];
    ans[h] = y + tr_query(t, cc[h]);
  }
  tt[i] = y == 0 ? 0 : tr_add_(t, 1 - 0, y - 1);
}
int main() {
  int n, q, h, i, j;
  srand_();
  scanf("%d", &n);
  for (i = 0; i < n; i++) {
    ej[i] = (int *)malloc(2 * sizeof *ej[i]);
    eh[i] = (int *)malloc(2 * sizeof *eh[i]);
  }
  for (h = 0; h < n - 1; h++) {
    scanf("%d%d", &i, &j), i--, j--;
    append(ej, eo, i, j), append(ej, eo, j, i);
  }
  scanf("%d", &q);
  for (h = 0; h < q; h++) {
    scanf("%d%d", &i, &cc[h]), i--;
    append(eh, eo_, i, h);
  }
  dfs(-1, 0);
  for (h = 0; h < q; h++) printf("%d\n", ans[h]);
  return 0;
}
