Padovan Sequence

Interview

Time limit1sMemory limit128 MB

Summary

For each test case, compute the Nth Padovan number defined by the spiral of equilateral triangles.

Level: Easy3 of 10
Topics: Dynamic programming, Array
Solved: No attempts yet

Problem

Equilateral triangles are attached one after another in a spiral. The first triangle has side length 1. After that, let $k$ be the length of the longest side of the spiral, and attach an equilateral triangle of side length $k$ to that side. This step repeats.

The Padovan sequence $P(N)$ is the side length of the $N$ -th triangle placed in the spiral. The first ten values, $P(1)$ through $P(10)$ , are 1, 1, 1, 2, 2, 3, 4, 5, 7, 9.

Given $N$ , write a program that computes $P(N)$ .

Input

The first line contains the number of test cases $T$ . Each test case is one line containing an integer $N$ . ( $1 \le N \le 100$ )

Output

For each test case, print $P(N)$ on its own line.

Examples1

Example 1
Input
```
2
6
12
```
Expected output
```
3
16
```