Vũ và Long được giao nhiệm vụ ra đề cho một kì thi lập trình. Trường của Vũ và Long có thể biểu diễn như một đồ thị cây gồm \(n\) phòng và \(n-1\) hành lang - từ một phòng bất kì có thể đến được tất cả những phòng khác thông qua những hành lang.

Sẽ có \(m\) ngày ra đề. Mỗi ngày Vũ và Long sẽ suy nghĩ đề ở trong \(2\) phòng khác nhau của trường, và cuối ngày sẽ họp nhau để thảo luận ở cùng một phòng. Vũ và Long muốn khoảng cách của phòng thảo luận tới \(2\) phòng mà họ suy nghĩ phải bằng nhau. Khoảng cách giữa \(2\) phòng bất kì được tính bằng số hành lang phải di chuyển.

Yêu cầu: với mỗi ngày, hãy giúp họ tìm ra số phòng thỏa mãn yêu cầu như trên.

Input

• Dòng đầu tiên chứa số \(n\) \((1 \le n \le 10^5)\) - số phòng của trường.
• \(n-1\) dòng sau thể hiện các hành lang. Dòng thứ \(i\) sẽ chứa \(2\) số \(a_i\) và \(b_i\) \((1 \le a_i, b_i \le n)\), mô tả hành lang thứ \(i\) sẽ kết nối \(2\) phòng \(a_i\) và \(b_i\).
• Dòng tiếp theo chứa \(m\) \((1 \le m \le 10^5)\) - số ngày để chuẩn bị cho kì thi.
• \(m\) dòng sau - dòng thứ \(j\) thể hiện câu truy vấn cho ngày thứ \(j\) gồm \(2\) số \(x_j\) và \(y_j\) \((1 \le x_j, y_j \le n)\) - \(2\) phòng mà Vũ và Long dùng để suy nghĩ đề.

Output

• In ra \(m\) dòng - dòng thứ \(j\) là số phòng thỏa mãn điều kiện vào ngày thứ \(j\).

Example

4
1 2
1 3
2 4
1
2 3

1

Constraints

• \(1 \le n \le 10^5\)
• \(1 \le m \le 10^5\)
• \(1 \le a_i, b_i, x_j, y_j \le n\)