CF2036F XORificator 3000

### 题面描述 多次询问，每次给定 $l,r,i,k$，求 $[l,r]$ 内所有满足 $x \not\equiv k\pmod{2^i}$ 的 $x$ 的异或和。

第一行一个整数 $t$，表示数据组数。 接下来 $t$ 组数据，每组数据一行四个整数表示 $l,r,i,k$。

对于每组数据输出一行一个整数表示答案。

保证 $1\le t\le 10^4$，$1\le l\le r\le 10^{18}$，$0\le i\le 30$，$0\le k < 2^i$。