푸아드

ACPC 운영위원회는 전국 대회 상위 7개 팀에게 금액이 같은 상금을 주고, 상금 총액을 후원사 배너에 적기로 했다. 배너에 적을 금액은 입체 숫자 조형물을 나란히 붙여서 나타낸다. 압둘라흐만 자말 아부엘카이르는 근처 가게에 남아 있던 숫자 조형물을 찾아내 물어보지도 않고 전부 사 왔다. 부지역 책임자 모하메드 푸아드는 사 온 조형물을 하나도 버리지 않기로 했다.

따라서 배너에 적는 금액은 사 온 숫자 조형물을 전부 한 번씩 쓴 수여야 하고, 7개 팀에 똑같이 나누어 주려면 7의 배수여야 한다. 주어진 숫자를 모두 사용해 만들 수 있는 7의 배수가 몇 개인지 세어라.

만든 수의 첫 자리는 0이 될 수 없다. 다만 조형물이 0 하나뿐이면 수 0을 만든 것으로 보고 유효한 수로 센다. 같은 숫자 조형물이 여러 개 있어서 배치만 다르고 값이 같은 수가 나오면 한 개로 센다.

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

이어지는 $T$개의 줄에 각 테스트 케이스가 하나씩 주어진다. 각 줄에는 사용할 숫자를 나타내는 문자열이 하나 있다. 이 문자열의 길이는 1 이상 9 이하이고, 각 문자는 '0'부터 '9'까지의 숫자다. 문자열은 0으로 시작할 수도 있다.

각 테스트 케이스마다 한 줄에 Case n: R 형식으로 출력한다. $n$은 1부터 시작하는 테스트 케이스 번호이고, $R$은 그 테스트 케이스의 숫자를 모두 사용해 만들 수 있는 7의 배수의 개수다.