비싼 저녁 식사

친구들이 모두 오늘 밤 저녁을 먹으러 식당에 간다. 친구들은 모두 수학을 아주 잘하지만, 모두 매우 이상하다. 1부터 시작하여, 당신의 $a^{th}$번째 친구는 식사의 총비용이 양의 정수이고 a로 나누어떨어지지 않으면 불쾌해한다.

친구들은 한 번에 한 명씩 식당에 들어간다. 누군가 식당에 들어오자마자 그 사람이 불쾌한 상태라면, 일행은 즉시 종업원을 부른다.

식당에 불쾌한 사람이 적어도 한 명 있는 동안에는, 그 불쾌한 사람들 중 한 명이 자신을 만족하게 만드는 가장 저렴한 항목을 구매한다. 식당에 불쾌한 사람이 아무도 없을 때까지 이 과정이 계속되고, 그러면 종업원이 떠난다. 다행히도 식당에서는 모든 정수 가격의 음식을 판매한다. 예시는 첫 번째 테스트 케이스의 설명을 참고하라.

친구들은 어떤 순서로든 식당에 들어올 수 있다. 종업원을 부른 뒤 식당에 불쾌한 사람이 한 명보다 많다면, 그 불쾌한 사람들 중 누구든 먼저 무언가를 구매할 수 있다. 이러한 선택들이 모두 이루어지는 방식에 따라 일행이 종업원을 부르는 횟수가 달라질 수 있다.

당신은 식당의 주인으로서 매우 피곤한 종업원들을 고용하고 있다. 당신은 친구들의 변동폭, 즉 친구들이 종업원을 부를 수 있는 최대 횟수와 최소 횟수의 차이를 계산하려 한다.

제한

메모리 제한: 1GB.

작은 데이터 세트 (테스트 세트 1 - 공개)

1 ≤ T ≤ 100. 1 ≤ N ≤ 1000. 시간 제한: 30초.

큰 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ T ≤ 1000. 1 ≤ N ≤ $10^{12}$. 시간 제한: 60초.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 각각 별도의 한 줄에 주어진다. 각 테스트 케이스에는 친구의 수를 나타내는 정수 N 하나가 주어진다.

각 테스트 케이스마다 "Case #x: y"을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이고(1부터 시작), y는 해당 테스트 케이스의 변동폭이다.

설명

케이스 #2에서 친구들이 $[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이다.