首先 $f(k)=\sum_{j=1}^k\lfloor1+\log_2 j\rfloor$ 可以在预处理后 $O(1)$ 计算。

设 $D(n)$ 构造 $n$ 个叶子的树的最小代价，则 $D(1)=f(1)$。$D(n)=f(n)+\min_{1\le k < n}\{f(k)+D(k)+D(n-k)\}$，这里 $k$ 是枚举其左子树的叶子个数，$f(k)$ 是因为不能出现连续的 $0$，因此要直接接 $01$。但注意如果 $k=1$ 则可以直接以 $0$ 结尾，不需要加上 $f(1)$。

可以证明 $D$ 是下凸函数，同时 $f$ 也是下凸函数，因此 $f(k)+D(k)+D(n-k)$ 也是下凸的，因此可以三分 $k$。

考虑从小到大枚举 $\delta$，不妨设当前求出了 $D(1),\ldots,D(n)$，则找到最大的 $m$ 使得 $D(m)=D(n)+\delta\cdot (m-n)$。这里的 $m$ 可以二分，且当 $n$ 足够大时，计算 $D(m)$ 不会用到未确定的 $D$ 值。经过尝试，在 $n\le 10^{15}$ 的范围中，$\delta$ 只有 $1840$。

计算出每个 $\delta$ 对应的区间后，每次询问可以用二分在 $O(\log \delta)$ 的时间内求出答案。