Team GCD

As the manager of Awesome Industries, its your job to group your employees into teams, so that they can work together well.

You have ~N~ employees, labelled from ~1~ to ~N~. Each employee has a "productivity", ~P_i~.

Every employee starts on their own team. Each day, two employees "team up", combining their two teams into one.

The "power" of a team is equal to the greatest common divisor (GCD) between the productivity of all members of the team.

Output the power of the newly formed team for each day.

Input

The first line of each test case consists of an integer ~N~ ~(1 \leq N \leq 10^5)~, the number of employees you have.

The next line consists of ~N~ integers ~P_i~ ~(1 \leq P_i \leq 10^8)~, where the ith integer is the "productivity" of the ith employee.

The next line consists of an integer ~T~ ~(1 \leq T \leq 10^5)~, the number of days employees are teaming up.

The next ~T~ lines are in the form ~i~ ~j~, indicating that the employees labelled ~i~ and ~j~ have teamed up.

Note: Two employees can team up multiple times in a single test case. You still need to output the power of their team for each day.

Output

Output the "power" of the newly-formed team, for each of the ~T~ days.

Example

Input

5
3 5 21 11 15
3
1 3
3 4
5 2

Output

3
1
5

• On Day 1, employees 1 (productivity = 3) and 3 (productivity = 21) team up. The new team contains employees ~{1,3}~, so its is ~GCD(P_1, P_3) = GCD(3, 21) = 3~

• On Day 2, employees 3 (productivity = 21) and 4 (productivity = 11) team up. The new team contains employees ~{1,3,4}~, so its "power" is ~GCD(P_1, P_3, P_4) = GCD(3, 21, 11) = 1~

• On Day 3, employees 2 (productivity = 5) and 5 (productivity = 15) team up. The new team contains employees ~{2,5}~, so its "power" is ~GCD(P_2, P_5) = GCD(5, 15) = 5~