The battle of Hogwarts is going to start very soon. Hermione has reviewed the whole strategy of the battle and she finds that they need to disable some wands of some death eaters. It is very difficult to perform magic without wands, so they will have some significant advantages over those death eaters. She quickly discovers that to disable a wand they have to know the sum of the magical numbers corresponding to that wand.

The properties of a magical number of a wand are given below:

1. The number must be greater than or equal to a certain number start.
2. The number must be less than or equal to a certain number end.
3. The binary representation of a magical number contains at most Maxone number of ones.
4. The binary representation of a magical number can differ from Ideal Number at not more than k positions. For example, 0110₂ (6₁₀) differs from 1010₂ (10₁₀) at two positions.
5. A magical number must be an integer which is divisible by 3, but not divisible by 7.

As both start and end can be quite large, she needs your help to find the sum of the magical numbers within this range.

Input starts with an integer T (≤ 130), denoting the number of test cases.

For each case, a single line follows which contains five integers: start, end, Maxone, Ideal Number, k respectively. All of them are non-negative integers and less than or equal to 10⁹. And start will not be greater than end.

For each case, print the case number and sum of the magical numbers.

For computing the number of positions of difference from the ideal number, both ideal number and magical number can be considered as 32 bit binary numbers with necessary number of leading zeros.