4534 - tiles

• Submit
• Status
• Discuss
• Summary

Description

2×n 안에 1×2 타일을 채워넣는 방법의 수는 몇 가지인지 계산해보자.

Input

Line 1: 입력 갯수 N (1 ≤ N ≤ 1000)

Line 2~N+1: 가로 길이 n (1 ≤ n ≤ 20)

Output

Line 1~N: 타일을 채우는 경우의 수

Sample Input

3
2
3
5

Sample Output

2
3
8

Hint

2×3 안에 1×2 타일을 채워넣는 방법은 3가지다.

 

타일을 채워넣는 방법의 수 = 맨 왼쪽에 세로로 넣는 방법의 수 + 맨 왼쪽에 가로로 넣는 방법의 수