write a go solution for E. Zebra-like Numberstime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputWe call a positive integer zebra-like if its binary representation has alternating bits up to the most significant bit, and the least significant bit is equal to 1. For example, the numbers 1, 5, and 21 are zebra-like, as their binary representations 1, 101, and 10101 meet the requirements, while the number 10 is not zebra-like, as the least significant bit of its binary representation 1010 is 0.We define the zebra value of a positive integer e as the minimum integer p such that e can be expressed as the sum of p zebra-like numbers (possibly the same, possibly different)Given three integers l, r, and k, calculate the number of integers x such that l<=x<=r and the zebra value of x equals k.InputEach test consists of several test cases. The first line contains a single integer t (1<=t<=100) — the number of test cases. The description of test cases follows.The only line of each test case contains three integers l, r (1<=l<=r<=10^18) and k (1<=k<=10^18).OutputFor each test case, output a single integer — the number of integers in [l,r] with zebra value k.ExampleInput51 100 31 1 115 77 22 10 1001234567 123456789101112131 12Output13
1
3
0
4246658701
NoteIn the first test case, there are 13 suitable numbers: 3,7,11,15,23,27,31,43,47,63,87,91,95. Each of them can be represented as a sum of 3 zebra-like numbers.. Output only the code with no comments, explanation, or additional text.