给定一个区间 [l,r] 和一个整数 k，其中 k 是 2 的非负整数次幂。请计算有多少个二元组 i,j(l≤i<j≤r)，满足 i XOR j 是k的倍数。

XOR：指位运算中的按位异或（Bitwise XOR），对两个整数的二进制表示按位进行异或运算。

输入

输入一行三个整数l,r,k(1 ≤ l < r ≤ 10^9, 1 ≤ k ≤ 10^9)
保证 k 是2的非负整数次幂。

输出

输出一行一个整数，表示满足条件的二元组数量。

样例

1 6 4

2

说明

解释：满足条件的二元组为 (1,5）和 (2,6)，它们的异或值均为 4。

1s, 1024KiB for each test case.