工业间谍在现代研究实验室中非常普遍。我就是这样一个工业间谍——别告诉任何人！我最近的任务是从一家著名的数学研究实验室窃取最新的发明。虽然很难直接获得他们的研究成果，但我从碎纸机里拿到了他们的废纸。

我已经重构出他们的研究课题是快速因数分解。但剩下的纸条碎片上只有单个数字，我无法想象它们是用来干什么的。难道这些数字能组成质数吗？请帮我找出利用给定的数字可以组成多少个不同的质数。

输入格式

输入的第一行包含测试用例的数量 $c$ ($1 \le c \le 200$)。每个测试用例由单行组成。该行包含纸条碎片上的数字（至少一个，最多七个）。

输出格式

对于每个测试用例，输出一行，包含通过重新排列这些数字可以重构出的不同质数的数量。在重构质数时，你可以忽略部分数字（例如，如果你有数字 7 和 1，你可以重构出三个质数：7、17 和 71）。重构出的数字如果（作为字符串表示时）仅因前导零而不同，则被视为相同的数字（参见样例输入中的第四个用例）。

样例

输入样例 1

4
17
1276543
9999999
011

输出样例 1

3
1336
0
2