# ZeroJudge - f711: 12218 - An Industrial Spy
### 題目連結：https://zerojudge.tw/ShowProblem?problemid=f711
###### tags: `ZeroJudge` `數學` `質數` `排列組合` `窮舉`

#include <iostream>
#include <string>
#include <set>
using namespace std;
#define SIZE 10000000

int primes[SIZE], primeAmount, digits[7], digitAmount, primeForms, nowNumber, nowSlots;
bool notPrime[SIZE] = { true, true }, picked[7] = {};
set <int> counted;

void Initialize() {
	for (int i = 2; i < SIZE; ++i) {
		if (!notPrime[i]) {
			primes[primeAmount] = i;
			++primeAmount;
		}
		for (int j = 0; i * primes[j] < SIZE; ++j) {
			notPrime[i * primes[j]] = true;
			if (!(i % primes[j]))
				break;
		}
	}
}

void PickDigits() {
	if (!nowSlots) {
		if (!notPrime[nowNumber] && counted.find(nowNumber) == counted.end()) {
			counted.insert(nowNumber);
			++primeForms;
		}
		return;
	}
	nowNumber = (nowNumber << 3) + (nowNumber << 1);
	for (int i = 0; i < digitAmount; ++i) 
		if (!picked[i]) {
			picked[i] = true; nowNumber += digits[i]; --nowSlots;
			PickDigits();
			picked[i] = false; nowNumber -= digits[i]; ++nowSlots;
		}
	nowNumber /= 10;
}

int main() {
	cin.sync_with_stdio(false); cin.tie(nullptr);
	string number;
	int times;
	Initialize();
	cin >> times;
	while (times--) {
		cin >> number;
		counted.clear();
		primeForms = 0; digitAmount = number.size();
		for (int i = 0; i != number.size(); ++i)
			digits[i] = number[i] - '0';
		for (nowSlots = 1; nowSlots <= digitAmount; ++nowSlots) 
			PickDigits();
		cout << primeForms << '\n';
	}
}