题目大意

给定一个长度为 n (1 ≤ n ≤ 20) 的正整数数组 {a₁, a₂, ..., aₙ}（1 ≤ aᵢ ≤ 100）。我们称一个非空子集 S ⊆ {1, ..., n} 为「亲密组」，当且仅当 ∏(i ∈ S) aᵢ 是一个完全平方数。求满足条件的子集个数。

通用思路

题目内容

小红定义一组是亲密数，当且仅当这组数的乘积是完全平方数。

现在小红拿到了一个数组，她希望选出若干个元素(不能一个都不选)使得它们是一组亲密数。小红想知道有多少种选择方案?

输入描述

第一行输入一个正整数 $n$ ，表示数组的长度。

第二行输入 $n$ 个正整数 $a_1,a_2,…,a_n$，表示数组。

$1≤n≤ 20$

$1 ≤ a_i ≤ 100$

输出描述

输出一个整数，表示有多少种选择方案。

样例1

输入

6
1 2 3 4 5 6

输出

7

说明

一共存在 $7$ 种方案：

选择元素 $[1]$

选择元素 $[4]$

选择元素 $[1,4]$

选择元素 $[2,3,6]$

选择元素 $[1,2,3,6]$

选择元素 $[4,2,3,6]$

选择元素 $[1,4,2,3,6]$