화염 분사관

록 페스티벌 무대에 화염을 뿜는 관 18개가 1번부터 18번까지 번호를 달고 설치되어 있다. 각 관은 정해진 밝기로 불꽃을 한 번 뿜는다.

그림 1: 관 번호

1번 관은 밝기 1을 낸다. $N > 1$일 때 $N$번 관은 $N-1$번 관의 두 배 밝기를 내므로, $N$번 관의 밝기는 $2^{N-1}$이다.

원하는 밝기를 내려면 여러 관을 동시에 발사한다. 이때 얻는 밝기는 발사한 관의 밝기를 모두 더한 값이고, 정수 $L$ 하나로 나타낸다. 제어 소프트웨어는 $L$을 입력으로 받아 어떤 관을 켜고 어떤 관을 끌지 정한다.

그림 2: 관의 상태

$L$이 정해지면 그 밝기를 내는 켜진 관의 조합은 단 하나다.

밸브가 굳거나 관이 막히면 요청한 조합을 그대로 발사하지 못한다. 그러면 관을 켜고 꺼서 다른 조합을 발사한다. 관 하나를 켜진 상태에서 꺼진 상태로, 또는 그 반대로 바꾸는 것을 상태 변경 한 번으로 센다.

그림 3: 요청한 관 상태(왼쪽)와 상태를 두 번 바꾼 조합(오른쪽)

그림 3의 두 조합은 두 군데가 다르다. 7번 관은 왼쪽에서 켜져 있고 오른쪽에서 꺼져 있으며, 8번 관은 왼쪽에서 꺼져 있고 오른쪽에서 켜져 있다.

그림 4: 요청한 관 상태(왼쪽)와 상태를 한 번 바꾼 조합(오른쪽)

그림 4의 왼쪽은 요청한 밝기가 45393일 때의 관 상태다. 오른쪽은 여기에 10번 관을 켠 것으로, 밝기는 45905가 된다.

제작진은 원래 값보다 밝기만 하면 다른 밝기도 받아들이기로 했다. 제작진이 공연에 예정한 $L$ 값 목록을 주면, 목록의 각 원래 값마다 다음 세 조건을 모두 만족하는 대체 $L$ 값이 몇 개인지 세어야 한다.

1. 대체 값은 원래 값보다 크다.
2. 대체 값은 주어진 목록에 있는 다른 값이다.
3. 대체 값은 원래 조합에서 관의 상태를 두 번 이하로 바꿔 만들 수 있다.

예정한 $L$ 값이 증가하는 순서로 한 줄에 하나씩 주어진다. 각 값은 $1 \le L \le 250000$을 만족하므로 값은 최대 250000개다. 마지막 줄에 -1이 하나 주어지고 입력이 끝난다.

원래 $L$ 값마다 주어진 순서대로 L:C 형식의 줄을 하나씩 출력한다. $L$은 원래 요청한 밝기이고, $C$는 위 세 조건을 만족하는 대체 값의 개수다. 콜론 앞뒤에 공백을 넣지 않는다.

정답을 내지만 제한 시간 안에 끝나지 않는 풀이가 있으므로 효율적인 알고리즘이 필요하다.