Ori Badpun，一个自以为是的矮人，用一个谜题嘲讽你：算法学家，嗯？很了解分治（divide and conquer），或者说 divide et impera 范式，嗯？或者你把它搞反了？！那么 impera et divide 或者“征服并划分”怎么样？定义一个数 $N$ 的“排列除数”（permutational divisor）为 $N$ 的一个真因子（即小于 $N$ 的因子），且该因子的数字是 $N$ 的数字的一个排列，且不允许有前导零。明白了吗？我将在 $T$ 次试验中测试你的技能。在每次试验中，你将得到一个正整数 $N$，你需要告诉我它有多少个排列除数。那么，你现在明白了吗？

输入的第一行包含测试用例的数量 $T$。接下来的 $T$ 行，每行包含一个自然数 $N$，你需要为该数确定答案。

数据范围：$1 \le T \le 100\,000$，$1 \le N \le 10^{18}$。

对于输入中的每个数，在单独的一行中输出一个整数，表示该数有多少个排列除数。

样例

输入格式 1

4
7
31
90
370521

输出格式 1

0
0
0
1

说明

数字 $370521$ 可以被 $123507$ 整除。