Regina is in charge of the latest social media campaign to advertise Amplitude!

There are ~n~ users that Regina could target as part of the campaign. Specifically, each user has a type of device and also a preferred social media application. As part of the campaign, Regina will target all users that either use a given type of device or a given social media application.

Regina has come up with ~q~ plans for how to run the campaign, each one specifying a specific type of device as well as a specific social media application. For each planned campaign, compute the number of users that would be targeted.

Constraints

~1 \le n \le 3 \cdot 10^5~

~1 \le q \le 3 \cdot 10^5~

~1 \le a_i, b_i, x_j, y_j \le n~

Subtask 1 [1 point]

~n \le 50~

~q \le n^2~

Subtask 2 [1 point]

No additional constraints.

Input Specification

The first line contains a single integer, ~n~.

The next ~n~ lines contain two integers, ~a_i~ and ~b_i~, indicating that the ~i^{\texttt{th}}~ user has device type ~a_i~ and uses social media application ~b_i~.

The next line contains a single integer, ~q~.

The next ~q~ lines contain two integers, ~x_j~ and ~y_j~, indicating that the ~j^{\texttt{th}}~ plan is to target all users that either have device type ~x_j~ or use social media application ~y_j~.

Output Specification

For each query, output a single integer, the number of users targeted.

Sample Input 1

4
1 1
1 1
1 2
3 1
3
1 1
4 2
4 3

Sample Output 1

4
1
0

Sample Explanation

For the first query, we want to count how many users have device type ~1~ or use social media application ~1~. The first three users have device type ~1~ and both the first and last user use social media application ~1~, so the answer is ~4~.

For the second query, we want to count how many users have device type ~4~ or use social media application ~2~. No one uses device type ~4~, and the third user uses social media application ~2~, so the answer is ~1~.

For the third query, we want to count how many users have device type ~4~ or use social media application ~3~. No such users do, so the answer is ~0~.