マルチテストについての説明はこちら (サンプル問題を確認されていない方のみお読みください。)

配点：$400$ 点

問題文

Judge 君と Contestant 君は数字当てゲーム「$n\text{-}$guesser」で遊びます．($n$ は正の整数)

$n\text{-}$guesser は次のようなゲームです：

• Judge 君が $0$ 以上 $n$ 以下の整数 $x$ (鍵と呼ぶことにする) を自由に決め，Contestant 君がその数字を当てる．
• Contestant 君と Judge 君とは次のような対話を何度でも行える：
  • Contestant 君が Judge 君に，実数 $q$ を自由に選び「$q$？」と質問する．
  • 「$q$？」と質問された Judge 君は， Contestant 君に $2$ 命題「$|q - x | < \frac{1}{2}$ である」および「$q \leq x$ である」の真偽をそれぞれ教える．

Contestant 君は以下の戦略を立てました：

• $2$ 実数 $l, r$ を用意し，はじめ $(l, r) = (0, n)$ とする．
• 対話が終了されるまで以下を繰り返す：
  • $q = \frac{1}{2}(l + r)$ として，Judge 君に「$q$？」と質問をする．
  • $|q - x| < \frac{1}{2}$ であるならば鍵である整数の値が確定するため，対話を終了する．
  • $| q - x | < \frac{1}{2}$ でなく，かつ $q \leq x$ ならば $l$ を $q$ で置換し，繰り返しの先頭に戻る．
  • $| q - x | < \frac{1}{2}$ でなく，かつ $q \leq x$ でないならば $r$ を $q$ で置換し，繰り返しの先頭に戻る．

Contestant 君は戦略通りにゲームをします．

また，Judge 君は整数 $X$ が好きなので，Judge 君が $n\text{-}$guesser ($\scriptsize n \geq X$) を行うとき，必ず鍵として整数 $X$ を選ぶことが分かっています．
なおこの情報はあなただけが知っています．(Contestant 君は知りません．)

$X\text{-}$guesser$, (X+1)\text{-}$guesser$, \ldots, n\text{-}$guesser $\scriptsize (n \geq X) \normalsize, \ldots$ のうち，Contestant 君の質問回数がちょうど $K$ 回になるようなものはいくつありますか？
求めてください．

なお，この問題の制約下で答えは有限個であることが示せます．

制約

• $1 \leq \Phi \leq 10^3$
• $1 \leq X < 2^{40}$
• $1 \leq K \leq 12$
• $X, K$ は整数

入力

各テストケースの入力は，それぞれ以下の形式で与えられる：

出力

答えを出力せよ．

サンプル

1
6 3

13

$\{\, 7, 9, 10, 15, 16, 17, 45, 46, 47, 48, 49, 50, 51 \,\}\text{-}$guesser が満たします．

たとえば $7\text{-}$guesser は次のように進行し，質問は $3$ 回行われます：

• Judge 君が鍵として $0$ 以上 $7$ 以下の整数 $x = 6 \,(= X)$ を決める．
• Contestant 君は $(l, r) = (0, 7)$ と初期化する．
• Contestant 君が「$\frac{7}{2} \, (= \frac{1}{2}(l + r))$？」と質問する．
  • Judge 君によって「$|\frac{7}{2} - x| < \frac{1}{2}$ ではない」かつ「$\frac{7}{2} \leq x$ である」ことが伝えられる．
  • Contestant 君は $(l, r) = (\frac{7}{2}, 7)$ と更新する．
• Contestant 君が「$\frac{21}{4} \, (= \frac{1}{2}(l + r))$？」と質問する．
  • Judge 君によって「$|\frac{21}{4} - x| < \frac{1}{2}$ ではない」かつ「$\frac{21}{4} \leq x$ である」ことが伝えられる．
  • Contestant 君は $(l, r) = (\frac{21}{4}, 7)$ と更新する．
• Contestant 君が「$\frac{49}{8} \, (= \frac{1}{2}(l + r))$？」と質問する．
  • Judge 君によって「$|\frac{49}{8} - x| < \frac{1}{2}$ である」かつ「$\frac{49}{8} \leq x$ ではない」ことが伝えられる．
  • Contestant 君は $x = \left\lfloor \frac{49}{8} \right\rfloor = 6$ であることを理解する．

3
141 1
1000 5
99824435 3

1
73
11