AT_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_1times p_2timesdotstimes p_n）。目前，在第（i）个城市，敌人的实力已经达到（2^{A_i}）或更高。找出出现在（T）个城镇中的每个敌人有多少个敌人的原始方块。

输入格式

输入以以下形式给出： ``` $T$ $L_1$ $A_1$ $L_2$ $A_2$ : $L_T$ $A_T$ ```

输出格式

打印 $(T)$ 行，$(i (1 \leqq i \leqq 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\\\$ 通りがあり得る。