Вам дається рядок \(S\) довжиною \(N\), що складається з цифр.

Знайдіть кількість квадратів чисел, які можна отримати, інтерпретуючи перестановку \(S\) як десяткове ціле число.

Більш формально, вирішіть наступне.

Нехай \(s_i\) ​ — число, що відповідає \(i\)-й цифрі \((1≤i≤N)\) від початку \(S\).

Знайдіть кількість квадратів чисел, які можна представити як \(\sum_{i=1}^N s_{p_i}10^{N-i}\) з перестановкою \(P=(p_1 ​,p_2 ​ ,…,p_N ​ )\) з \((1,…,N)\).

Обмеження

• \(1≤N≤13\)
• \(S\) — рядок довжиною \(N\), що складається з цифр.
• \(N\) є цілим числом.

Формат вхідних даних

Перший рядок містить ціле число \(N\).

Наступний   рядок містить \(S\).

Формат вихідних даних

У вихідний потік виведіть відповідь.

Приклад вхідних даних

4
4320

Приклад вихідних даних

2

Для \(P=(4,2,3,1)\) ми маємо \(s_4 ​ ×10^3+s_2 ​ ×10^2+s_3 ​ ×10^1+s_1 ​ =324=18^2\) .

Для \(P=(3,2,4,1)\) ми маємо \(s_3 ​ ×10^3+s_2 ​ ×10^2+s_4 ​ ×10^1+s_1 ​ =2304=48^2\) .

Жодні інші перестановки не призводять до квадратів чисел, тому вам слід вивести 2.

Приклад вхідних даних

3
010

Приклад вихідних даних

2

Для \(P=(1,3,2)\) or \(P=(3,1,2)\), маємо \(\displaystyle\sum _ {i=1} ^ Ns _ {p _ i}10 ^ {N-i}=1=1 ^ 2\).
Для \(P=(2,1,3)\) or \(P=(2,3,1)\), маємо \(\displaystyle\sum _ {i=1} ^ Ns _ {p _ i}10 ^ {N-i}=100=10 ^ 2\).

Приклад вхідних даних

13
8694027811503

Приклад вихідних даних

840