눌러서 잠금 해제
시간 제한1초메모리 제한128 MB
버튼이 B개일 때, 사용되는 버튼들을 서로소인 순서 있는 조합들로 나누는 방법의 수를 구하는 문제입니다.
문제
어떤 도어락에는 1번부터 B번까지 번호가 붙은 B개의 버튼이 있다. 여기서 1 <= B <= 11이다. 비밀번호는 하나 이상의 버튼 조합을 정해진 순서대로 누른 뒤 손잡이를 돌리는 방식으로 입력한다.
버튼 조합은 한 번에 동시에 누르는 하나 이상의 버튼 집합이다. 하나의 버튼이 어떤 조합에 사용되면, 같은 비밀번호의 다른 조합에는 다시 사용할 수 없다. 어떤 버튼은 비밀번호에 사용하지 않아도 된다.
B=8일 때 (1-2-3)(4)(7-8)은 세 조합 (1-2-3), (4), (7-8)을 순서대로 누르는 올바른 비밀번호이다. 버튼 5와 6은 사용하지 않았다. 반면 (1-2-3)(2-4)(5-6)은 버튼 2가 두 조합에 중복으로 사용되므로 올바른 비밀번호가 아니다.
여러 도어락의 버튼 개수 B가 주어질 때, 각 도어락마다 만들 수 있는 서로 다른 비밀번호의 개수를 구하라.
입력
첫 줄에 도어락의 개수 N이 주어진다. 1 <= N <= 100이다.
다음 N개의 줄에는 각 도어락의 버튼 개수 B가 하나씩 주어진다.
출력
각 도어락마다 만들 수 있는 비밀번호의 개수를 입력 순서대로 한 줄에 하나씩 출력한다.