import math
from itertools import permutations


def is_prime(x):
    if x < 2:
        return False

    for i in range(2, int(math.sqrt(x)) + 1):
        if x % i == 0:
            return False

    return True


def solution(numbers):
    # 주어진 문자열로 만들 수 있는 모든 조합 생성
    # set으로 중복처리
    #   1. 조합이 중복되는 경우(ex. "011" -> ("0", "1", "1") -> ("0", "1"))
    #   2. 결과가 중복되는 경우(ex. "1" -> 1, "01" -> 1)
    answer = set()

    for i in range(1, len(numbers) + 1):
        for perm in set(permutations(numbers, i)):
            num = int(''.join(perm))
            if is_prime(num):
                answer.add(num)

    return len(answer)


# 정확성  테스트
# 테스트 1 〉	통과 (0.05ms, 10.4MB)
# 테스트 2 〉	통과 (2.29ms, 10.4MB)
# 테스트 3 〉	통과 (0.02ms, 10.3MB)
# 테스트 4 〉	통과 (0.25ms, 10.3MB)
# 테스트 5 〉	통과 (0.84ms, 10.4MB)
# 테스트 6 〉	통과 (0.02ms, 10.5MB)
# 테스트 7 〉	통과 (0.05ms, 10.2MB)
# 테스트 8 〉	통과 (0.93ms, 10.3MB)
# 테스트 9 〉	통과 (0.04ms, 10.3MB)
# 테스트 10 〉	통과 (6.10ms, 10.4MB)
# 테스트 11 〉	통과 (0.51ms, 10.4MB)
# 테스트 12 〉	통과 (0.33ms, 10.3MB)
# 채점 결과
# 정확성: 100.0
# 합계: 100.0 / 100.0

assert (solution("17") == 3)
assert (solution("011") == 2)
