You are given an array $a$ of integers. But there is something special about these integers. All of the integers are square free. Formally, for each $i$, if  $a_{i} = p_{1}^{q_{1}} * p_{2}^{q_{2}}*...*p_{m}^{q_{2}}$  where every $p_j (1 \le j \le m)$ is a prime, then $q_j \le 1$.
Coming to the problem, You need to find the number of subarrays where the maximum number of the subarray is also the LCM (Least Common Multiple) of the subarray.

Input Format

• The first line contains a single integer $T -$ the number of test cases.
• The first line of each test case contains a single integer $n -$the size of the array.
• The next line contains $n$ square free integers.

Output Format

• For each test, output the number of subarrays that fullfil the condition.

Constraints

• $1 \le T \le 100$
• $1 \le n \le 10^5$
• $1 \le a_i \le 10^5$ for each $i$ from $1$ to $n$.
• The sum of $n$ over all test cases does not exceed $10^5$.