산업 스파이의 편지

안녕하세요. 저는 산업 스파이입니다. 제 정체는 절대 아무에게도 말하지 말아 주세요.

저의 가장 최근 임무는 어느 유명한 수학 연구소의 최신 연구 결과를 빼내는 것이었습니다. 저는 실력 있는 산업 스파이라 자료를 손에 넣는 것 자체는 어렵지 않았습니다. 그런데 연구소는 제가 올 것을 눈치챘는지, 연구 결과를 모두 문서 세단기에 넣어 버렸습니다. 어쩔 수 없이 저는 잘게 잘린 종이 조각을 전부 챙겨 나올 수밖에 없었습니다.

저를 고용한 사람은 매우 무서운 사람이고, 저 또한 프로이기에 실수는 용납할 수 없습니다. 어떻게든 이 자료를 복원해야 합니다. 이 연구소의 연구 주제는 빠른 소인수분해입니다. 제가 가진 종이 조각에는 숫자가 한 자리씩만 적혀 있는데, 원래 수가 무엇이었는지 도무지 알 수 없습니다.

종이 조각에 적힌 숫자들을 알려 드릴 테니, 이 조각들을 적절히 배열해서 만들 수 있는 소수가 몇 개인지 알려 주실 수 있을까요?

감사합니다.

스파이 드림.

첫째 줄에 테스트 케이스의 개수 $c$가 주어진다. ($1 \le c \le 200$)

각 테스트 케이스는 한 줄로 이루어지며, 종이 조각에 적힌 숫자들이 공백 없이 주어진다. 종이 조각은 최소 $1$개, 최대 $7$개이다.

각 테스트 케이스마다, 종이 조각을 적절히 배열하여 만들 수 있는 서로 다른 소수의 개수를 출력한다. 이때 모든 종이 조각을 사용하지 않아도 된다.

예를 들어 $7$과 $1$이 있으면 만들 수 있는 소수는 $7$, $17$, $71$이다.

조각을 배열하여 만든 수가 $0$으로 시작하는 경우, 맨 앞의 $0$들을 지운 값이 같으면 서로 같은 수로 간주한다.