解题思路

把 $x$ 的数字重排得到 $y$，且 $y$ 不能有前导 0。等价于：在与 $x$ 同位数的完全平方数里，统计数字频次与 $x$ 完全一致的个数。做法：

1. 记位数 $L$，枚举所有平方 $s=r^2$ 落在 $[10^{L-1},\,10^L-1]$；
2. 用长度为 10 的数组统计数字频次（0~9），与 $x$ 的频次比较，相同则计入答案。 直接枚举平方避免前导 0 且天然去重。

复杂度分析

题目内容

Bingbong 特别喜欢完全平方数。

现在给定一个整数 $x$，你可以任意打乱数位，得到新的数字 $y$ ，要求打乱后不能存在前导 $0$ 。

Bingbong 希望 $y$ 是一个完全平方数，请你帮他计算一下共有多少种不同的 $y$ 。

请注意：两种不同的操作方案，若结果相同则是属于同一种。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1≤ T ≤ 100)$ 代表数据组数，每组测试数据描述如下：

一个整数 $x(1 ≦ x ≦ 10^9)$ ，为给定的数字。

输出描述

输出包含 $T$ 行，每行一个整数，表示不同的结果个数。

样例1

输入

2
414
1

输出

2
1