Mr. X is Vice-president of FIFA. He wants to arrange a worldwide football tournament. There is no group stage in this tournament and all match will be played knockout system(The player loss will eliminate ).

Its time for making fixure. First he need to calculate number of match will have.But he has not enough time for calculaing.So he ask you for write a programme for calculate the number of match if N player perticipate in the tournament.

Input

First line contains one integer T denotes the number of  testcase.

Then the following T(1<=T<=1000) lines contains an integer  N (2<=N<=10^18) - number of participants (N must be represented as 2^x where x=1,2,3….).

Output

For each case, print the case number and number of match need to arrange

Example

Input:
2
2
4

Output:
Case 1: 1
Case 2: 3