Description

小方塊喜歡玩方塊遊戲，他最近發現了一款新的方塊遊戲。在這個遊戲中，有五種物品：原木、木材、木炭、木棍和火把。小方塊現在手上有 $N$ 個原木，他很喜歡火把，所以他希望利用這些原木做出盡量多的火把。小方塊要怎麼做出火把呢？他有兩種操作可以做：合成和熔煉。

合成：根據配方消耗需要的材料，就能獲得指定的物品。以下是所有的合成配方，消耗箭頭左邊的物品，就能獲得右邊的物品。

1 個原木 → 4 個木材

2 個木材 → 4 個木棍

1 個木棍和 1 個木炭 → 1 個火把
熔煉：1 次熔煉可以將 1 個原木變成 1 個木炭，不過必須要消耗 1 點能量。獲得能量的方式是消耗燃料，除了火把以外的物品都可以當作燃料，下表是每種物品當作燃料消耗後可以獲得的能量點數：

燃料能量

1 個原木 1 點

1 個木材 1 點

1 個木棍 0.2 點

1 個木炭 8 點

注意如果要把一個物品當成燃料消耗，就必須把那整個物品當成燃料消耗掉，例如你不能只消耗 $1 / 8$ 個木炭獲得 1 點能量。

燃料	能量
1 個原木	1 點
1 個木材	1 點
1 個木棍	0.2 點
1 個木炭	8 點

舉例來說，如果小方塊一開始有 10 個原木，那他可以先把 3 個原木合成成 $3 \times 4 = 12$ 個木材，把其中 7 個木材當成燃料後獲得 7 點能量，用來把剩下的 7 個原木熔煉成木炭，再將剩下 5 個木材的其中 4 個合成成 $\frac{4}{2} \times 4 = 8$ 個木棍，最終用其中 7 個木棍和 7 個原木合成出 7 個火把。

請告訴小方塊，他最多可以做出幾個火把。

Input Format

第一行包含一個整數 $T$ ，代表測試資料的數量。

接下來有 $T$ 行，每一行是一筆測試資料。一筆測試資料包含一個整數 $N$ ，代表小方塊有幾個原木。

$1 \leq T \leq 10^{5}$
$1 \leq N \leq 10^{12}$

Output Format

輸出 $T$ 行，其中第 $i$ 行輸出一個整數，代表第 $i$ 筆測試資料的答案。

Sample Input 1

14
1
2
3
4
5
6
7
8
9
10
100
271828182845
314159265359
1000000000000

Sample Output 1

0
1
2
2
3
4
4
5
6
7
78
214399693511
247787589578
788732394365

Hints

Problem Source

Subtasks

No.	Testdata Range	Constraints	Score
1	0	範例測資	0
2	0~17	無額外限制	100

Testdata and Limits

No.	Time Limit (ms)	Memory Limit (VSS, KiB)	Output Limit (KiB)	Subtasks
0	1000	524288	65536	1 2
1	1000	524288	65536	2
2	1000	524288	65536	2
3	1000	524288	65536	2
4	1000	524288	65536	2
5	1000	524288	65536	2
6	1000	524288	65536	2
7	1000	524288	65536	2
8	1000	524288	65536	2
9	1000	524288	65536	2
10	1000	524288	65536	2
11	1000	524288	65536	2
12	1000	524288	65536	2
13	1000	524288	65536	2
14	1000	524288	65536	2
15	1000	524288	65536	2
16	1000	524288	65536	2
17	1000	524288	65536	2

Submit out of contest

1 個原木	→	4 個木材
2 個木材	→	4 個木棍
1 個木棍和 1 個木炭	→	1 個火把

880 . 火把製造者