TopCoder

拉菲好可愛 >////<
迷子でもいい、迷子でも進め!

User's AC Ratio

75.0% (3/4)

Submission's AC Ratio

66.7% (4/6)

Tags

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 點能量。

舉例來說,如果小方塊一開始有 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