시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 5 5 2 100.000%

문제

한국 최고의 자물쇠 회사 마선영은 도어락을 생산한다. 이 도어락은 B(1 ≤ B ≤ 11)개의 버튼으로 이루어졌으며 각 버튼은 '1'부터 'B'까지 이름 붙여 있다. 도어락은 버튼 조합으로 이뤄진 비밀번호를 올바른 순서로 누른 후 손잡이를 돌리면 마법처럼-_- 열린다

버튼 조합은 한 개 이상의 버튼을 동시에 누르는 것이다. 비밀번호는 최소 한 개 이상의 이러한 버튼 조합들로 이뤄져 있다. 어떤 버튼을 한 조합에서 사용하면, 다른 조합에서는 사용할 수 없다. 아래는 B=8인 예이다.

(1-2-3)(4)(7-8)

위는 (1-2-3), (4), (7-8)의 조합 세 개로 이뤄진 올바른 비밀번호이다. 버튼 5와 6은 이 비밀번호에 사용하지 않았다.

(1-2-3)(2-4)(5-6)

위는 버튼 2가 조합 (1-2-3)과 (2-4)에 두 번 나왔기 때문에 올바른 비밀번호가 아니다.

마선영의 CEO인 김선영은 정선영에게 B개의 버튼이 있을 때, 가능한 비밀번호의 수를 구하는 프로그램을 작성해 달라고 부탁했다. 프로그램은 고객의 도어락 리스트를 받아 주문 번호와 B값, 가능한 비밀번호 수를 출력해야 한다. 도어락 리스트는 최소 한 개, 최대 백 개의 도어락을 포함하고 있다.

정선영이 만들어야 하는 프로그램을 우리가 대신 만들어보자.

입력

첫 줄은 도어락 개수인 정수 N(1 ≤ N ≤ 100)이 주어진다. 다음 줄부터 N개의 도어락 버튼의 개수 B가 주어진다.

출력

각각의 도어락마다 가능한 비밀번호의 개수를 한 줄에 하나씩 출력한다.

예제 입력

3
3
4
3

예제 출력

25
149
25

힌트