#3324. 「SNOI2020」取石子

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: EntropyIncreaser

题目描述

甲乙两个人玩取石子游戏。他们面前有一堆共 n 个石子,然后由甲先手,两人轮流从中取走石子:甲第一次取走的个数不能超过 k ,接下来每个人取走的个数不能超过上一个人刚刚取走个数的 2 倍。每人每次必须至少取一个石子。取走最后一个石子的人失败,另一方获胜。现在已知 k ,请你求出在 1 N 中有多少整数 n 使得甲在 n 颗石子的游戏中有必胜策略。

输入格式

多组数据。

第一行一个正整数 T 表示数据组数。

接下来 T 行每行两个用空格隔开的整数 k, N ,表示一组询问。

输出格式

输出 T 行,按照输入顺序,每行一个整数表示答案。

样例

样例输入

3
1 5
2 5
1 10

样例输出

2
3
4

样例解释

k=1 时:

  • 如果 n=1 ,甲只能取走唯一一颗石子从而失败。
  • 如果 n=2 ,甲取走一颗石子,乙只能取走最后一颗石子,甲获胜。
  • 如果 n=3 ,甲只能取走一颗石子,乙再取走一颗石子,甲只能取走最后一颗石子从而失败。
  • 如果 n=4 ,甲只能取走一颗石子,乙再取走两颗石子,甲只能取走最后一颗石子从而失败。
  • 如果 n=5 ,甲只能取走一颗石子,乙只能取走一颗或两颗石子,甲总能再留给乙留下最后一颗石子从而获胜。

数据范围与提示

对于所有数据, 1\le T\le 10^5, k, N\le 10^{18}

  • 对于 10\% 的数据, T,N\le 500
  • 对于另外 20\% 的数据, T, N\le 10^5
  • 对于另外 20\% 的数据, T\le 3, N\le 3\times 10^6
  • 对于另外 20\% 的数据, k=1
  • 对于余下 30\% 的数据,无特殊限制。