Description

One day, LHR studied the Fibonacci sequence $f(n)$.

$f(n)$ is defined as follows:

$$f(n)= \left\{\begin{matrix} 1 &n==1\parallel n==2\\ f(n-2)+f(n-1) &n\ge 3 \end{matrix}\right. $$

LHR created LHR sequence $L(n)$ based on $f(n)$ because she was sleepy.

Since LHR need to go to bed, she only gave the first $100$ items of $L(n)$ which are

$$ [1,1,2,2,3,3,3,5,5,5,\\ 5,5,8,8,8,8,8,8,8,8,\\ 1,3,1,3, 1,3, 1,3, 1,3,\\ 1,3,1,3,1,3, 1,3, 1,3,\\ 1,3,1,3,1,3,2,1,2,1,\\ 2,1,2,1,2,1,2,1,2,1,\\ 2,1,2,1,2,1,2,1,2,1,\\ 2,1,2,1,2,1,2,1,2,1,\\ 2,1,2,1,2,1,2,1,3,4,\\ 3,4,3,4, 3,4,3,4,3,4 ]$$

After LHR wakes up, she wants to know the value of $L(n)$, can you help her?

Format

Input

The first line of input is an integer $T(1\le T\le 10^{5})$.

$T$ lines followed, each line has an integer $n(1\le n\le 10^{9})$.

Output

For each $n$, you need to ouput $L(n)$.

Samples

100
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

1
1
2
2
3
3
3
5
5
5
5
5
8
8
8
8
8
8
8
8
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
3
4
3
4
3
4
3
4
3
4
3
4