U168149 Jack 的钻石

“得手!”黑帮老大Jack在手下的帮助下，成功带着一大包的钻石回到了自己的据点现在如何分配这些钻石成了一个棘手的难题。

有 $n$ 名黑帮成员，为了方便，分别编号为 $1$ 到 $n$。并且假设老大编号为 $n$。开始，Jack 老大应把战利品拿出来给大家过目，并提出一个分配方案，然后所有 $n$ 名成员（含自己）分别表示赞同或不赞同，如果不赞同的成员比例严格大于一半，那么根据规矩，老大 Jack 就会被处理掉，由编号为 $n-1$ 的成员维任，并依照同样的过程继续分配刚才的战利品，否则这个分配过程就完成了。在黑帮团伙中成员们的目的都比较单纯，所有成员首先要保住自己的性命，在能保住性命的前提下，当然要拿尽可能多的钻石: 一旦在当前这个方案里，他拿到的钻石数不大于之后所有情况下可能拿到的最大钻石数，那么他就会反对当前分配方案，否则支持。 这个黑帮是一一个理性的黑帮（不然早就被端掉了），因此你可以认为所有成员都是无穷阶理性的，也就是说每个人都知道其他人也拥有与自己相同的想法，在任意步过后也同样追求最优解，并且计算上不会出错。 Jack 老大在尝试制定不同的分配原则，因此有时他要求自己必须要分配到至少 $1$ 个，而有时不需要，现在他想知道为了满足分配规则和保住他的性命，钻石至少要有多少个。

无

无

题目来源：[CF690A1](https://www.luogu.com.cn/problem/CF690A1), [CF690A2](https://www.luogu.com.cn/problem/CF690A2) 对于 $100\%$ 的数据，$T\le 10^5$, $1\le n\le 10^9$, $S\in \{0, 1\}$。