解题思路

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

复杂度分析

2000ms

Difficulty: 4

所属公司 : 中国电信

算法与标签>暴力枚举

Bingbong 特别喜欢完全平方数。

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

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

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

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

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

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

输入

2
414
1

输出

2
1

输入

预期输出（选填）