Alice 和她的弟弟 Bob 正在玩一個猜數字遊戲。
Bob 選擇了一個（隱藏的）整數 $S$。
Alice 可以詢問關於這個隱藏數字的問題，形式如下：「隱藏數字是否至少為 $x$？」Bob 會用「是」或「否」來回答她的問題。不幸的是，在詢問了 $K \ge 1$ 個問題後，Bob 對這個遊戲感到厭倦，從那時起，他對所有問題都會給出錯誤的回答。
也就是說，Bob： 對於前 $K$ 個問題，回答「是」若且唯若 $x \le S$。 在第 $K$ 個問題之後，回答「是」若且唯若 $S < x$。
請注意，Bob 對前 $K$ 個問題總是回答正確，且 Alice 不知道 $K$ 的值。
你的任務是設計並實作一個詢問策略，讓 Alice 能夠識別出隱藏數字。你的分數取決於詢問問題的數量——詢問次數越少，分數越高。
實作細節
你應該實作以下程序：
long long play_game()- 對於每個測試案例，此程序最多會被呼叫 $T$ 次。
- 該程序應透過呼叫以下程序來詢問關於隱藏數字的問題，並找出並回傳隱藏數字 $S$：
bool ask(long long x)- $x$：指定 Alice 問題的數字。
- $x$ 的值必須在 $1$ 到 $10^{18}$ 之間（含）。
- 該程序回傳一個布林值，代表 Bob 的回答。
- 在每次
play_game的呼叫中，此程序最多可被呼叫 $150$ 次。
評測系統的行為是適應性的（adaptive），這意味著在某些測試中，$S$ 和 $K$ 的值在呼叫 play_game 之前並未固定。保證至少存在一對 $(S, K)$ 使得評測系統的回答是一致的。
資料範圍
- $1 \le T \le 1000$
- $1 \le S \le 10^{18}$
- $1 \le K \le 150$
子任務
如果你的解法不符合上述實作細節，或者 play_game 回傳的值即使在單次呼叫中不正確，你的解法將獲得 $0$ 分。
否則，令 $C$ 為你的解法在所有 play_game 呼叫中所詢問問題的最大數量。你的分數根據下表計算：
| 條件 | 分數 |
|---|---|
| $132 < C \le 150$ | $20 \cdot (\frac{150-C}{18})^2$ |
| $78 < C \le 132$ | $20 + 20 \cdot (\frac{132-C}{54})^2$ |
| $72 < C \le 78$ | $40 + 30 \cdot (\frac{78-C}{6})^2$ |
| $67 < C \le 72$ | $70 + 30 \cdot (\frac{72-C}{5})^2$ |
| $C \le 67$ | $100$ |
說明
考慮一個隱藏整數 $S = 2$ 且 $K = 1$ 的場景。遊戲以呼叫 play_game() 開始：
假設 play_game 首先呼叫 ask(2)。由於 $2 \le S = 2$ 且此時 Bob 說的是實話，該呼叫回傳 true。
假設 play_game 再次呼叫 ask(2)。雖然條件 $2 \le S = 2$ 仍然成立，但 Bob 現在在說謊（因為他已經說了 $K = 1$ 次實話），所以該呼叫回傳 false。收到對同一個問題的矛盾回答，揭示了 Bob 在隨後的所有回答中都會說謊。
現在假設 play_game 呼叫 ask(3)。由於 $3 \le S = 2$ 為假，且 Bob 在說謊，該呼叫回傳 true。此時，我們可以推斷出 $2 \le S < 3$，這意味著 $S = 2$。
因此，該程序應回傳 $2$。
範例評測程式
範例評測程式不是適應性的。它處理 $T$ 個場景，並在每個案例中從輸入讀取固定的 $S$ 和 $K$ 值，並據此回答問題。
輸入格式：
T S[0] K[0] S[1] K[1] ... S[T-1] K[T-1]
這裡 $S[i]$ 和 $K[i]$ ($0 \le i < T$) 指定了每次呼叫 play_game 的隱藏參數。
輸出格式：
G[0] C[0] G[1] C[1] ... G[T-1] C[T-1]
這裡 $G[i]$ ($0 \le i < T$) 是當隱藏參數為 $S[i]$ 和 $K[i]$ 時 play_game 回傳的數字，$C[i]$ 是該次呼叫期間詢問的問題數量。