눌러서 잠금 해제

어떤 도어락에는 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가 하나씩 주어진다.

각 도어락마다 만들 수 있는 비밀번호의 개수를 입력 순서대로 한 줄에 하나씩 출력한다.