Deadly! 60-Note Combo

Deadly! 60-Note Combo is a rhythm game developed by Seongmo. In this game, a song always consists of 60 notes, and the only judgments for each note are GOOD (1) and MISS (0). Like any rhythm game, Deadly! 60-Note Combo has a combo system. A GOOD judgment is worth a base score of 1 point, and 2 additional points are added for each combo accumulated. In other words, if the combo at the moment a GOOD judgment is given is X, you get 2X-1 points. A MISS judgment resets the combo and gives no points. For example, if the result of hitting 5 notes is 11101, the score is 1 + 3 + 5 + 0 + 1 = 10.

Every player's play record is stored on the server. The result of hitting the 60 notes is uploaded to the server as a single number read in binary. For example, if only the last 4 notes are judged GOOD and all other judgments are MISS, the number representing this play is 1111(2) = 15. After long work, Seongmo finished developing the server's ranking system and only testing remains. To check whether it can handle many people's play records, Seongmo created test data in which every play record from a to b is sent to the server one by one, and then checks the rank of the person whose play record is c. However, Seongmo could not fill in what the rank should actually be. Help Seongmo complete the test data!

The rank is defined as (the number of people with a higher score than mine) + 1. For example, if the scores of 5 people are 3, 2, 2, 1, and 1, the person with 3 points is rank 1, the two people with 2 points are rank 2, and the two people with 1 point are rank 4.

The first line gives the number of test cases T. (1 ≤ T ≤ 300,000)

Each of the following T lines gives integers a, b, c. (0 ≤ a ≤ c ≤ b < 2^60)

For each test case, print the answer on its own line.