The IJN headquarters has intercepted a telegram from the Abyssal Fleet; your naval base is about to be bombed.

Although you are a battle-hardened admiral with many land-based aircraft and rocket interceptors, having just cleared E6 Hard and possessing Atlanta along with the highest-rate anti-air CI, you decide to use only Atlanta to defend against the incoming air raids.

Your naval base can be modeled as a tree. The Abyssal bombing occurs between two points (the order of the start and end points does not matter), and the bombing path is the simple path on the tree. In other words, there are a total of $C_n^2$ possible bombing scenarios.

Your Atlanta has different anti-air values on different edges. The number of remaining Abyssal aircraft is the $\gcd$ of all anti-air values along the path minus 1. When this value becomes 0, you have successfully defended against the Abyssal bombing.

You want to know how many possible bombing scenarios exist such that you can successfully defend.

Unfortunately, Atlanta is new to the base, and her anti-air values are somewhat unstable. There will be $Q$ changes to the anti-air values, where each change refers to the anti-air value of a specific edge being modified.

Please calculate the answers for all $Q + 1$ scenarios.

Input

The first line contains an integer $n$.

The next $n - 1$ lines each contain three integers $u, v, w$, representing that the anti-air value of the edge between nodes $u$ and $v$ is $w$.

The next line contains an integer $Q$.

The next $Q$ lines each contain two integers $k, x$, representing that the anti-air value of the $k$-th edge read (1-indexed) is changed to $x$.

Output

Output $Q + 1$ lines, each containing an integer.

These represent the answers for the initial state, the state after the first change, ..., and the state after the $Q$-th change, respectively.

Examples

Input 1

6
2 1 3
2 3 2
4 1 7
2 5 3
6 3 9
4
1 6
1 9
4 3
2 9

Output 1

9
8
9
9
4

Note

For all data, $2 \le n \le 10^5$, $Q \le 100$, $1 \le w, x \le 10^6$.

For 10% of the data, $n \le 300$.

For 30% of the data, $n \le 1000$.

For 70% of the data, $n \le 7000$.