Dynamic programming approach for finding perfect square subsequence
Let us assume first that by subsequence you mean non-contiguous subsequence.

There are 10 primes in the range $1,\ldots,29$:
$$ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. $$
You can represent each number in the range $1,\ldots,29$ as a vector of length 10 of exponents. A set of such vectors correspond to numbers whose product is a perfect square iff they sum to a vector whose entries are all even. Alternatively, if we think of the exponents modulo 2, then a set of such vectors correspond to numbers whose product is a perfect square iff they sum to zero.

This suggests the following algorithm. Construct a matrix whose rows correspond to the vectors outlined above (modulo 2), and determine its rank. From the rank you can compute the size of the kernel, which is the quantity you’re after.



Suppose now that you’re after contiguous subsequences.

Let $b_i = a_1 \cdot a_2 \cdots a_i$. The subsequence $a_i,\ldots,a_j$ multiplies to a perfect square iff $b_j/b_{i-1}$ is a perfect square, which happens if the vectors corresponding to $b_{i-1}$ and $b_j$ are equal.

This suggests the following algorithm. Compute the vectors corresponding to each $b_i$ (do this by computing the vectors for $a_i$ and summing them as you go), sort them (you can represent them as 10-bit integers in an arbitrary way), and divide them into runs of length $c_1,\ldots,c_\ell$. The answer is then $\sum_i \binom{c_i}{2}$.