#P6791. [SNOI2020] 取石子

[SNOI2020] 取石子

题目描述

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

输入格式

多组数据。

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

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

输出格式

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

3
1 5
2 5
1 10
2
3
4

提示

样例说明

对于样例 11,当 k=1k=1 时:

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

数据说明与提示

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

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