配点: 100 点
問題文
你是一名职业钢琴家,这个月你将在茨城县各地举办的运动会上弹钢琴。茨城县的钢琴是高桥风格创造的特殊类型,具有以下特点。
- 88 按键水平排列,所有按键均为正整数。
刻有 1 。从左边开始
对于除 1, 2 以外的按键,刻印的整数为 1 用左键盘 2 等于左键的总和。
- 例如,从左开始 1, 2 第 3, 2 , 从第 3 号开始, 5, 7, 12, 19, ... 等等。
- 1 三个或更多键的组合称为“和弦”。尤其是彼此相邻 2 不包含调的和弦称为“美丽和弦”。
- 例如,“从左边 1, 3, 6, 88 第”或“从左边算起 5 th”是一个美丽的和弦,但是“从左边 5, 7, 8 th”不是一个优美的和弦。
- 和弦的“高桥值”表示为刻在构成和弦的琴键上的整数之和。
- 例如,从左开始 i 刻入密钥的整数 A_i 如果设置``从左 由“ 86, 9, 1, 20 th”组成的和弦的高桥值是 相当于 A_{86} + A_9 + A_1 + A_{20} 。
整个运动会 执行 Q 次。 i 第二届运动会主办学校成立 X_i 既然是周年纪念,你应该知道高桥值是 我决定将 X_i 这样美丽的和弦交织到歌曲中。 i 从第一个运动会弹奏的钢琴左侧开始 1, 2 每个键都有一个 因为我们知道刻有 a_i, b_i ,所以每个 对于 i ,给定钢琴的 Takahashi 值是 请告诉我有多少个像 X_i 这样优美的和弦。
入力
1 行显示提出的问题数。 给出了 Q 。 跨越
2 第 Q 线,i 第一届运动会信息 a_i, b_i, X_i 用空格分隔。
Q a_1 b_1 X_1 a_2 b_2 X_2 a_3 b_3 X_3 ... a_Q b_Q X_Q
出力
总而言之 请输出 Q 行。 请输出第 i 行中, i 题的答案。
制約
- 1 \leq Q \leq 100000
- 1 \leq a_i, b_i, X_i \leq 10^{17}
- 所有输入均为整数
小課題
小課題 1 [11 点]
- Q \leq 100 很满意。
- 全部 对于 i , a_i = b_i = 1, X_i \leq 10 很满意。
小課題 2 [31 点]
- Q \leq 100 很满意。
- X_i \leq 1000 \times b_i 很满意。
小課題 3 [58 点]
- 没有其他限制。 给出
入力例 1
2 1 1 1 1 1 9
出力例 1
2 2
入力例 2
3 1 2 32 5 2 1 2 1 70
出力例 2
1 0 2