B. Strange Definitiontime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputLet us call two integers x and y adjacent if \frac{lcm(x, y)}{gcd(x, y)} is a perfect square. For example, 3 and 12 are adjacent, but 6 and 9 are not.Here gcd(x, y) denotes the greatest common divisor (GCD) of integers x and y, and lcm(x, y) denotes the least common multiple (LCM) of integers x and y.You are given an array a of length n. Each second the following happens: each element a_i of the array is replaced by the product of all elements of the array (including itself), that are adjacent to the current value. Let d_i be the number of adjacent elements to a_i (including a_i itself). The beauty of the array is defined as \max_{1 \le i \le n} d_i. You are given q queries: each query is described by an integer w, and you have to output the beauty of the array after w seconds.InputThe first input line contains a single integer t (1 \le t \le 10^5) — the number of test cases.The first line of each test case contains a single integer n (1 \le n \le 3 \cdot 10^5) — the length of the array.The following line contains n integers a_1, \ldots, a_n (1 \le a_i \le 10^6) — array elements. The next line contain a single integer q (1 \le q \le 3 \cdot 10^5) — the number of queries.The following q lines contain a single integer w each (0 \le w \le 10^{18}) — the queries themselves.It is guaranteed that the sum of values n over all test cases does not exceed 3 \cdot 10^5, and the sum of values q over all test cases does not exceed 3 \cdot 10^5OutputFor each query output a single integer — the beauty of the array at the corresponding moment.ExampleInput
2
4
6 8 4 2
1
0
6
12 3 20 5 80 1
1
1
Output
2
3
NoteIn the first test case, the initial array contains elements [6, 8, 4, 2]. Element a_4=2 in this array is adjacent to a_4=2 (since \frac{lcm(2, 2)}{gcd(2, 2)}=\frac{2}{2}=1=1^2) and a_2=8 (since \frac{lcm(8,2)}{gcd(8, 2)}=\frac{8}{2}=4=2^2). Hence, d_4=2, and this is the maximal possible value d_i in this array.In the second test case, the initial array contains elements [12, 3, 20, 5, 80, 1]. The elements adjacent to 12 are \{12, 3\}, the elements adjacent to 3 are \{12, 3\}, the elements adjacent to 20 are \{20, 5, 80\}, the elements adjacent to 5 are \{20, 5, 80\}, the elements adjacent to 80 are \{20, 5, 80\}, the elements adjacent to 1 are \{1\}. After one second, the array is transformed into [36, 36, 8000, 8000, 8000, 1].
2
4
6 8 4 2
1
0
6
12 3 20 5 80 1
1
1

2 3 
['bitmasks', 'graphs', 'hashing', 'math', 'number theory', '*1900']