AT_iroha2019_day4_d 揺れる街、増える敵

[problemUrl]: https://atcoder.jp/contests/iroha2019-day4/tasks/iroha2019_day4_d \\(T\\) 個の街で、それぞれ敵が出現した。 \\(i\\) 番目の街で出現した敵は、一列に並んだマス状の形をしており、元々のマスの個数は \\(1\\) 個以上 \\(L\_i\\) 個以下である。 街ではすでに敵のマスのうち \\(0\\) 個以上を破壊し、敵は破壊されたマスで分割されたいくつかの部分に分かれている。マスの個数が \\(L\\) の敵は、端から \\(i\\) 番目のマスを破壊されると、マスの個数がそれぞれ \\(i-1\\) と \\(L-i\\) の \\(2\\) つの敵に分割される(ただし、マスの個数が \\(0\\) の敵は消滅する)。 しかし、その敵は分割されると強くなってしまうものだった。具体的には、マスの個数が \\(p\_1, p\_2, \\dots, p\_n\\) である \\(n\\) 個の部分に分割されたとき、敵の強さは全体で \\(p\_1\\times p\_2\\times\\dots\\times p\_n\\) になってしまう。 現在、\\(i\\) 番目の街では敵の強さが \\(2^{A\_i}\\) 以上になってしまったという。敵の元々のマスの個数としてありうるものが何通りあるかを、\\(T\\) 個の街に現れた敵それぞれについて求めよ。

入力は以下の形式で与えられる。 ``` \(T\) \(L_1\) \(A_1\) \(L_2\) \(A_2\) : \(L_T\) \(A_T\) ```

\\(T\\) 行出力し、\\(i\\ (1≦i≦T)\\) 行目には \\(i\\) 番目の街に出現した敵に対する答えを出力せよ。

### ストーリー 「いったい、なんだったんでしょうか…」帰り道、いろはちゃんがぽつぽつと話し始める。 「さっきの化け物、明らかにおかしいです」「あんなの、この世界にいていいものじゃありません」「あれはまるで、バグ…」 彼女の言葉を遮るように、轟音が響き渡った。しかも、今度は何回も。僕たちは顔を見合わせ、走り出した。 ### 制約 - 入力はすべて整数 - \\(1≦T≦300\\) - \\(1≦L\_i≦10^9,\\ 0≦A\_i≦10^9\\) ### 解説 [解説](https://img.atcoder.jp/iroha2019-day4/editorial-D.pdf) ### Sample Explanation 1 \\\\(1\\\\) 番目の街に出現した敵の元々のマスの個数は \\\\(7, 8, 9\\\\) の \\\\(3\\\\) 通りがあり得る。 それぞれ、敵が次のように破壊されたの場合に条件を満たす(`o`はマスが破壊されていないことを、`x`は破壊されていることを表す)。 - 敵の元々のマスの個数が \\\\(7\\\\) : `ooxoooo` (敵の強さは \\\\(8\\\\)) - 敵の元々のマスの個数が \\\\(8\\\\) : `ooxooxoo` (敵の強さは \\\\(8\\\\)) - 敵の元々のマスの個数が \\\\(9\\\\) : `oooxoxooo` (敵の強さは \\\\(9\\\\)) \\\\(2\\\\) 番目の街に出現した敵の元々のマスの個数は \\\\(9, 10, 11, 12, 13\\\\) の \\\\(5\\\\) 通りがあり得る。 それぞれ、次のような破壊のされ方の場合に条件を満たす。 - 敵の元々のマスの個数が \\\\(9\\\\) : `ooooxoooo` (敵の強さは \\\\(16\\\\)) - 敵の元々のマスの個数が \\\\(10\\\\) : `ooxooxoooo` (敵の強さは \\\\(16\\\\)) - 敵の元々のマスの個数が \\\\(11\\\\) : `oooxooooxoo` (敵の強さは \\\\(24\\\\)) - 敵の元々のマスの個数が \\\\(12\\\\) : `oooooooooxoo` (敵の強さは \\\\(18\\\\)) - 敵の元々のマスの個数が \\\\(13\\\\) : `ooooxoooooooo` (敵の強さは \\\\(32\\\\)) \\\\(3\\\\) 番目の街に出現した敵の元々のマスの個数は \\\\(0\\\\) 通りがあり得る。