//这是经典的DFS深度搜索的问题,要找到搜索结束的条件是什么,以及由于排列不可以是重复的,
//因此需要剪枝,同时每个数组中的元素只能选择一次,因此需要一个辅助数组visits
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
int res=0;
//设置全局变量表示总共找到的可行的方案数
int n;
const int N=13;
bool visits[N];
int nums[N];
bool is_square(int x){//自定义函数用来判断是否为平方数
return x>-1&&sqrt(x)==(int)sqrt(x);
}
void DFS(vector<int>&path){
if(path.size()==n+1){
res++;
return;
}
for(int i=0;i<n;i++){
if(i>0&&nums[i]==nums[i-1]&&visits[i-1]==false)
continue;//在这里进行剪枝对全排列去重
if((!visits[i]&&path.back()==-1)||(path.back()>=0&&is_square(nums[i]+path.back())&&!visits[i])){
visits[i]=true;
path.push_back(nums[i]);
DFS(path);
visits[i]=false;
path.pop_back();//进行回溯
}
}
}
int main(){
cin>>n;
for(int i=0;i<n;i++){
cin>>nums[i];
}
sort(nums,nums+n);
vector<int> path;
path.push_back(-1);
DFS(path);
cout<<res<<endl;
}