Problem Description

时间回到，初中，午后。

早上的数学课，小 hua 刚刚学会一次函数，她已经洞悉其本质。

刚刚的上机课，小 hua 刚刚学会异或运算，运用却已经是炉火纯青。

于是小 hua 出招，给定**正整数** $k, b,c,v$，请问有多少**非负整数** $x$ 满足令 $p_x = kx+b$ 有 $p_x \oplus c \leq v$。

小 pang 随手破解，却见小 hua 嘴角仍有一丝笑意：“加上多测，又如何呢？”

Input

第一行正整数 $T$，表示有 $T$ 组数据。

接下来 $T$ 行，每行 $4$ 个正整数，分别是 $k,b,c,v$。

Output

$T$ 行，每行一个非负整数表示答案。

5
1 0 0 10
5 4 114 514
871 234 12893 43298
7 488998 432432 894032
2 14839204384343 189403284932043287 876543210000000000

11
103
51
57862
438264185397807830

Hint

对于所有数据，$1\leq T\leq 2\times 10^5$，$1\leq k,b,c,v\leq 10^{18}$，均为正整数。