비싼 저녁 식사 (Small)

오늘 저녁, 친구들이 모두 같은 식당에 모인다. 친구들은 계산이 빠르지만 하나같이 까다롭다. $a$번 친구는(번호는 1부터 시작한다) 지금까지 주문한 음식값의 합계가 양의 정수이면서 $a$의 배수여야 만족하고, 그렇지 않으면 불만이다.

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

식당 안에 불만인 사람이 한 명이라도 있으면, 그중 한 명이 자기를 만족시키는 가장 싼 음식을 산다. 즉 합계가 그 사람 번호의 다음 배수까지 올라간다. 이 일은 식당 안의 누구도 불만이 아닐 때까지 반복되고, 그러면 종업원은 자리를 뜬다. 식당은 모든 정수 가격의 음식을 팔기 때문에 어떤 금액이든 정확히 쓸 수 있다.

아직 아무도 아무것도 사지 않았을 때 합계는 0이고, 0은 양의 정수가 아니므로 가장 먼저 들어온 사람은 언제나 불만이다.

친구들이 들어오는 순서는 어떤 순서든 될 수 있다. 종업원을 부른 뒤 불만인 사람이 여럿이면 그중 누가 먼저 음식을 살지도 정해져 있지 않다. 이런 선택에 따라 종업원을 부르는 횟수가 달라진다.

식당 주인인 당신의 종업원은 지쳐 있다. 친구가 $N$명일 때, 종업원을 부르는 횟수의 최댓값과 최솟값의 차이를 구하라.

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

제한

• $1 \le T \le 100$
• $1 \le N \le 1000$

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

$N = 3$인 경우를 보자. 들어오는 순서가 1, 2, 3이라고 하자. 1번이 들어와 불만이므로 종업원을 부르고 가격이 1인 음식을 사서 합계가 1이 된다. 이제 불만인 사람이 없다. 다음으로 2번이 들어와 불만이므로 종업원을 부르고 가격이 1인 음식을 사서 합계가 2가 된다. 역시 불만인 사람이 없다. 마지막으로 3번이 들어와 불만이므로 종업원을 부르고 가격이 1인 음식을 사서 합계가 3이 된다. 그러면 2번이 불만이 되어 가격이 1인 음식을 사서 합계가 4가 되고, 이어서 3번이 불만이 되어 가격이 2인 음식을 사서 합계가 6이 된다. 더 이상 불만인 사람이 없고 종업원은 세 번 불렸다.

순서가 3, 1, 2이면 어떻게 되는지 보자. 3번이 들어와 불만이므로 종업원을 부르고 가격이 3인 음식을 사서 합계가 3이 된다. 다음으로 1번이 들어오지만 불만인 사람은 없다. 마지막으로 2번이 들어와 불만이므로 종업원을 부르고 가격이 1인 음식을 사서 합계가 4가 된다. 그러면 3번이 불만이 되어 가격이 2인 음식을 사서 합계가 6이 된다. 불만인 사람이 없고 종업원은 두 번 불렸다. 따라서 $N = 3$의 답은 1이다.