题目描述

小 Z 在数学课上学到关于完全平方数的概念：若一个数能表示成某个整数的平方的形式，则称这个数为完全平方数。比如 $1=1 \times 1$，$4=2 \times 2$，$9=3 \times 3$。现在给出一个数字串 $S$，如果将这个数字串打乱重新组合（前导不为 $0$），请你帮小 Z 算一算有多少个完全平方数。

注意：$0$ 也算完全平方数。

输入格式

第一行，一个整数，表示数字串 $S$ 的长度 $N$。$1 \le N \le 13$。

第二行，一个 $N$ 位的字符串，表示数字串 $S$。

输出格式

一行，一个整数，表示得出的完全平方的个数。

4
4320

2

3
010

2

13
8694027811503

840