Định nghĩa kỳ lạ

Ta gọi hai số nguyên dương $x$ và $y$ là kề nhau nếu ${\displaystyle \frac{lcm(x,y)}{gcd(x,y)}}$ là một số chính phương. Ví dụ, $3$ và $12$ kề nhau (vì $\frac{lcm(3,12)}{gcd(3,12)}=\frac{12}{3}=4=2^2$), nhưng $6$ và $9$ thì không.

Ở đây $gcd(x,y)$ là ước chung lớn nhất và $lcm(x,y)$ là bội chung nhỏ nhất của $x$ và $y$.

Cho một mảng $a$ gồm $n$ phần tử. Mỗi giây, đồng thời với mọi $i$, phần tử $a_i$ được thay thế bởi tích của tất cả các phần tử của mảng (kể cả chính nó) mà kề với giá trị hiện tại của $a_i$.

Gọi $d_i$ là số phần tử kề với $a_i$ (bao gồm cả chính $a_i$). Độ đẹp của mảng được định nghĩa là ${max}_{1\le i\le n}{d}_i$.

Cho $q$ truy vấn, mỗi truy vấn là một số nguyên $w$: hãy in ra độ đẹp của mảng sau $w$ giây.

Dữ liệu vào

• Dòng đầu chứa một số nguyên $t$ — số lượng bộ dữ liệu.
• Với mỗi bộ dữ liệu:
  • Dòng đầu chứa số nguyên $n$ — độ dài mảng.
  • Dòng tiếp theo chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.
  • Dòng tiếp theo chứa số nguyên $q$ — số truy vấn.
  • $q$ dòng tiếp theo, mỗi dòng chứa một số nguyên $w$ — truy vấn.

Dữ liệu ra

Với mỗi truy vấn, in ra trên một dòng độ đẹp của mảng tại thời điểm tương ứng.

Ràng buộc

• $1\le t\le {10}^5$
• $1\le n\le 3·{10}^5$
• $1\le a_i\le {10}^6$
• $1\le q\le 3·{10}^5$
• $0\le w\le {10}^{18}$
• Tổng $n$ trên tất cả các bộ dữ liệu không vượt quá $3·{10}^5$.
• Tổng $q$ trên tất cả các bộ dữ liệu không vượt quá $3·{10}^5$.

Ví dụ