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. 
/*/ Author: kal013 /*/
// #pragma GCC optimize ("O3")
#include "bits/stdc++.h"
#include "ext/pb_ds/assoc_container.hpp"
#include "ext/pb_ds/tree_policy.hpp"
using namespace std;
using namespace __gnu_pbds;

template<class T> 
using ordered_set = tree<T, null_type,less<T>, rb_tree_tag, tree_order_statistics_node_update> ;

template<class key, class value, class cmp = std::less<key>>
using ordered_map = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;
// find_by_order(k)  returns iterator to kth element starting from 0;
// order_of_key(k) returns count of elements strictly smaller than k;

template<class T>
using min_heap = priority_queue<T,vector<T>,greater<T> >; 

/*/---------------------------IO(Debugging)----------------------/*/
template<class T> istream& operator >> (istream &is, vector<T>& V) {
    for(auto &e : V)
        is >> e;
    return is;
}
template<class T, size_t N> istream& operator >> (istream &is, array<T, N>& V) {
    for(auto &e : V)
        is >> e;
    return is;
}
#ifdef __SIZEOF_INT128__
ostream& operator << (ostream &os, __int128 const& value){
    static char buffer[64];
    int index = 0;
    __uint128_t T = (value < 0) ? (-(value + 1)) + __uint128_t(1) : value;
    if (value < 0) 
        os << '-';
    else if (T == 0)
        return os << '0';
    for(; T > 0; ++index){
        buffer[index] = static_cast<char>('0' + (T % 10));
        T /= 10;
    }    
    while(index > 0)
        os << buffer[--index];
    return os;
}
istream& operator >> (istream& is, __int128& T){
    static char buffer[64];
    is >> buffer;
    size_t len = strlen(buffer), index = 0;
    T = 0; int mul = 1;
    if (buffer[index] == '-')
        ++index, mul *= -1;
    for(; index < len; ++index)
        T = T * 10 + static_cast<int>(buffer[index] - '0');
    T *= mul;    
    return is;
}
#endif
template<typename CharT, typename Traits, typename T>
ostream& _containerprint(std::basic_ostream<CharT, Traits> &out, T const &val) {
    return (out << val << " ");
}
template<typename CharT, typename Traits, typename T1, typename T2>
ostream& _containerprint(std::basic_ostream<CharT, Traits> &out, pair<T1, T2> const &val) {
    return (out << "(" << val.first << "," << val.second << ") ");
}
template<typename CharT, typename Traits, template<typename, typename...> class TT, typename... Args>
ostream& operator << (std::basic_ostream<CharT, Traits> &out, TT<Args...> const &cont) {
    out << "[ ";
    for(auto&& elem : cont) _containerprint(out, elem);
    return (out << "]");
}
template<class L, class R> ostream& operator << (ostream& out, pair<L, R> const &val){
    return (out << "(" << val.first << "," << val.second << ") ");
}
template<typename L, size_t N> ostream& operator << (ostream& out, array<L, N> const &cont){
    out << "[ ";
    for(auto&& elem : cont) _containerprint(out, elem);
    return (out << "]");    
}
template<class T> ostream& operator<<(ostream &out, ordered_set<T> const& S){
    out << "{ ";
    for(const auto& s:S) out << s << " ";
    return (out << "}");
}
template<class L, class R, class chash = std::hash<L> > ostream& operator << (ostream &out, gp_hash_table<L, R, chash> const& M) {
    out << "{ ";
    for(const auto& m: M) out << "(" << m.first << ":" << m.second << ") ";
    return (out << "}");
}
template<class P, class Q = vector<P>, class R = less<P> > ostream& operator << (ostream& out, priority_queue<P, Q, R> const& M){
    static priority_queue<P, Q, R> U;
    U = M;
    out << "{ ";
    while(!U.empty())
        out << U.top() << " ", U.pop();
    return (out << "}");
}
template<class P> ostream& operator << (ostream& out, queue<P> const& M){
    static queue<P> U;
    U = M;
    out << "{ ";
    while(!U.empty())
        out << U.front() << " ", U.pop();
    return (out << "}");
}
#define TRACE
#ifdef TRACE
    #define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
    template <typename Arg1>
    void __f(const char* name, Arg1&& arg1){
        cerr << name << " : " << arg1 << endl;
    }
    template <typename Arg1, typename... Args>
    void __f(const char* names, Arg1&& arg1, Args&&... args){
        const char* comma = strchr(names + 1, ',');
        cerr.write(names, comma - names) << " : " << arg1<<" | ";
        __f(comma+1, args...);
    }
#else
    #define trace(...) 1
#endif

/*/---------------------------RNG----------------------/*/
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
inline int64_t random_long(long long l = LLONG_MIN,long long r = LLONG_MAX){
    uniform_int_distribution<int64_t> generator(l,r);
    return generator(rng);
}
struct custom_hash { // Credits: https://codeforces.com/blog/entry/62393
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
    template<typename L, typename R>
    size_t operator()(pair<L,R> const& Y) const{
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(Y.first * 31ull + Y.second + FIXED_RANDOM);
    }
};

/*/---------------------------Defines----------------------/*/
#define ll long long
#define endl "\n"
#define all(v) (v).begin(),(v).end()
/*/-----------------------Modular Arithmetic---------------/*/
const int mod = 1e9 + 7;

/*/-----------------------------Code begins----------------------------------/*/

const ll is_query = -(1LL<<63);
struct Line {
	ll m, b;
	mutable function<const Line*()> succ;
	bool operator<(const Line& rhs) const {
		if (rhs.b != is_query) return m < rhs.m;
		const Line* s = succ(); if(!s)return 0;
		ll x = rhs.m; return b-s->b < (s->m -m)*x;}
}; // will maintain upper hull for maximum
struct HullDynamic : public multiset<Line> { 
	bool bad(iterator y) { auto z = next(y);
		if (y == begin()) { if (z == end()) return 0;
			return y->m == z->m && y->b <= z->b;
		} auto x = prev(y);
		if (z==end())return y->m==x->m && y->b <= x->b;
		// return frac2(x->b-y->b , y->b-z->b , y->m-x->m , z->m-y->m)>=0; //prevents overflow
		return (x->b - y->b)* (__int128)(z->m - y->m) >= (y->b - z->b)* (__int128)(y->m - x->m);
	}
	void insert_line(ll m, ll b) {
		auto y = insert({ m, b });
		y->succ = [=] { return next(y) == end() ? 0 : &*next(y); };
		if (bad(y)) { erase(y); return; }
		while (next(y) != end() && bad(next(y))) erase(next(y));
		while (y != begin() && bad(prev(y))) erase(prev(y));
	}
	ll eval(ll x) {
		auto l = *lower_bound((Line) { x, is_query });
		return l.m * x + l.b; }
};

const int N = 2e5 + 100;
vector<int> adj[N];
int c[N], sub[N], depth[N];

int P[N];
vector<array<int, 2>> queries[N];
void dfs(int n, int p){
	sub[n] = 1;
	depth[n] = depth[p] + 1;
	P[n] = p;
	for(auto e: adj[n]){
		if (e == p)
			continue;
		++c[n];
		dfs(e, n);
		sub[n] += sub[e];
	}
}

const int K = 512;
vector<int> values[N];

void dfs2(int n, int p){
	values[n].resize(min(sub[n], K));
	for(auto e: adj[n]){
		if (e == p)
			continue;
		dfs2(e, n);
		for(int j = 0; j < values[n].size(); ++j){
			if (j < values[e].size()){
				values[n][j] += max(values[e][j] + c[e] - 1 - j, 0);
			}
			else{
				values[n][j] += max(c[e] - 1 - j, 0);
			}
		}
	}
	while (!values[n].empty() && values[n].back() == 0){
		values[n].pop_back();
	}
	values[n].shrink_to_fit();
}

int TOT;
int dfs3(int n, int k, int d){
	assert (k >= K);
	if (k * 1LL * (depth[n] - d + 2) > TOT){
		return 0;	
	}
	if (values[n].size() < K)
		return 0;
	int tmp = c[n] - 1 - k;
	for(auto e: adj[n]){
		if (e == P[n] || sub[e] <= k){
			continue;
		}
		tmp += max(c[e] - 1 - k + dfs3(e, k, d), 0);
	}
	return max(tmp, 0);
}

void solve(){
 	int n;
 	cin >> n;
 	TOT = n;
 	for(int i = 1; i < n; ++i){
 		int u, v;
 		cin >> u >> v;
 		adj[u].push_back(v);
 		adj[v].push_back(u);
 	}
 	dfs(1, 0);
 	dfs2(1, 0);

 	for(int i = 1; i <= n; ++i){
 		sort(all(adj[i]), [&] (int x, int y){
 			if (P[i] == x)
 				return false;
 			if (P[i] == y)
 				return true;
 			return sub[x] > sub[y];
 		});
 	}
 	int q;
 	cin >> q;
 	for(int j = 0; j < q; ++j){
 		int v, k;
 		cin >> v >> k;
 		int ans = -1;
 		if (k < values[v].size()){
 			ans = c[v] + values[v][k];
 		}
 		else if (values[v].size() < K){
			ans = c[v];
 		}
 		else{
 			ans = c[v] + dfs3(v, k, depth[v]);
 		}
 		if (ans > n){
 			cout << v << " " << k << endl;
 		}
 		else{
 			cout << ans << endl;
 		}
 	}



}
int main(){
    // Use "set_name".max_load_factor(0.25);"set_name".reserve(512); with unordered set
    // Or use gp_hash_table<X,null_type>
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cout << fixed << setprecision(25);
    cerr << fixed << setprecision(10);
    auto start = std::chrono::high_resolution_clock::now();

    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }

    auto stop = std::chrono::high_resolution_clock::now(); 
    auto duration = std::chrono::duration_cast<std::chrono::nanoseconds>(stop - start);
    // cerr << "Time taken : " << ((long double)duration.count())/((long double) 1e9) <<"s "<< endl;     
}