비싼 저녁 식사 (큰 입력)

오늘 저녁, 친구들이 모두 한 식당에 모인다. 친구들은 수학을 아주 잘하지만 성미가 유별나다. 1번부터 번호를 매길 때, $a$번 친구는 지금까지 주문한 음식값의 합이 양의 정수이면서 $a$의 배수일 때만 만족한다. 그렇지 않으면 불만이다.

친구들은 한 명씩 차례로 식당에 들어온다. 누군가 들어온 순간에 그 사람이 불만이면 일행은 즉시 종업원을 부른다.

식당 안에 불만인 사람이 한 명이라도 있는 동안, 그중 한 명이 자기가 만족하게 되는 가장 싼 음식을 하나 산다. 이 과정은 식당 안에 불만인 사람이 아무도 남지 않을 때까지 이어지고, 그러면 종업원은 자리를 뜬다. 식당은 모든 양의 정숫값 가격의 음식을 판다.

친구들이 들어오는 순서는 어떤 순서든 될 수 있다. 종업원을 부른 뒤에 불만인 사람이 둘 이상이면, 그중 누구든 먼저 음식을 살 수 있다. 이런 선택에 따라 일행이 종업원을 부르는 횟수가 달라진다.

식당 주인인 당신은 종업원들이 몹시 지쳐 있어서 친구들의 격차를 알고 싶다. 격차는 친구들이 종업원을 부를 수 있는 최대 횟수와 최소 횟수의 차이다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 다음 $T$개의 줄에 테스트 케이스가 한 줄에 하나씩 주어진다. 각 줄에는 친구의 수 $N$이 정수 하나로 주어진다.

제한

• $1 \le T \le 1000$
• $1 \le N \le 10^{12}$

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 그 테스트 케이스의 격차이다.

$N = 3$인 경우를 보자. 친구들이 [1, 2, 3] 순서로 들어온다고 하면 이렇게 진행된다. 1번이 들어와 불만이므로 종업원을 부르고, 값이 1인 음식을 산다. 이제 아무도 불만이 아니다. 다음으로 2번이 들어와 불만이므로 종업원을 부르고, 값이 1인 음식을 사서 합계가 2가 된다. 이제 아무도 불만이 아니다. 다음으로 3번이 들어와 불만이므로 종업원을 부르고, 값이 1인 음식을 사서 합계가 3이 된다. 그러자 2번이 불만이 되어 값이 1인 음식을 사고, 합계가 4가 된다. 그러자 3번이 불만이 되어 값이 2인 음식을 사고, 합계가 6이 된다. 마침내 아무도 불만이 아니게 되었고, 종업원은 세 번 불렸다.

대신 친구들이 [3, 1, 2] 순서로 들어온다고 하자. 3번이 들어와 불만이므로 종업원을 부르고, 값이 3인 음식을 산다. 이제 아무도 불만이 아니다. 다음으로 1번이 들어오지만 불만인 사람은 없다. 다음으로 2번이 들어와 불만이므로 종업원을 부르고, 값이 1인 음식을 사서 합계가 4가 된다. 그러자 3번이 불만이 되어 값이 2인 음식을 사고, 합계가 6이 된다. 이제 아무도 불만이 아니고, 종업원은 두 번 불렸다. 따라서 격차는 1이다.