#1773 단어 조합

67  1 s   128 MB  

Description

K개의 문자로 이루어진 문자열 S가 있다.

이 문자열 S를 이루는 문자를 재조합하여 만들수 있는 문자열 S′의 개수를 세는 프로그램을 작성하라. ( S 자기 자신도 S′에 포함된다고 가정한다. )
예를 들어 문자열 ‘aabc’를 재조합하여 만들 수 있는 문자열 S′은 다음과 같이 총 12개이다.
 
S′ = {aabc, aacb, abac, abca, acab, acba, baac, baca, bcaa, caab, caba, cbaa}

Input

맨 처음 테스트 케이스의 수 T 가 들어온다. ( 1 ≤ T ≤ 50 ) 그 다음 T 줄만큼 문자열 S가 들어오며, S의 길이는 1이상 10이하 이다. 문자열 S는 영문 소문자로만 이루어져 있다고 가정한다.

Output

각 테스트 케이스마다 문자열 S로 만들 수 있는 S′의 갯수를 출력한다.

Sample Input

Sample Output

2
ab
aabc
2
12

Source

2011 Ajou University Programming Contest, Division 2