사탕 가게 (작은 입력)

사탕 가게를 운영하려면 최적화할 일이 끝없이 나온다. 요즘 가장 잘 팔리는 사탕은 위즈보퍼다. 위즈보퍼는 아주 빨리 상하기 때문에 다음 두 가지 제약이 따른다.

• 매일 아침 공급업자에게서 위즈보퍼를 새로 사와야 한다.
• 그날 아침에 사온 상자로만 위즈보퍼를 팔아야 한다.

공급업자에게는 무게가 그램 단위 정수인 상자라면 어떤 무게든 주문할 수 있다. 상자는 쪼갤 수 없어서 손님에게는 상자를 통째로 건넨다.

하루에 손님은 최대 $k$명 오고, 첫 번째 손님부터 순서대로 위즈보퍼에 쓸 금액을 $1$센트 이상 $C$센트 이하의 정수로 고른다. 위즈보퍼는 $1$그램당 $1$센트이므로 $4$센트를 쓰겠다는 손님에게는 정확히 $4$그램을 줘야 한다. $4$그램짜리 상자 하나를 줘도 되고, $2$그램짜리 하나와 $1$그램짜리 둘을 줘도 된다.

손님이 어떤 금액을 고르더라도 모든 손님에게 원하는 무게를 정확히 줄 수 있어야 한다. 아침에 주문해야 하는 상자 개수의 최솟값을 구하라.

참고: 손님이 금액을 고르는 시점에 앞선 손님이 무엇을 사갔는지는 알지만, 뒤에 올 손님이 무엇을 살지는 모른다.

예를 들어 $k=2$, $C=2$라면 $1$그램짜리 상자 넷을 사도 되지만, $1$그램짜리 둘과 $2$그램짜리 하나, 즉 상자 셋으로도 충분하다.

• 첫 손님이 $2$센트를 쓰면 $2$그램짜리를 준다. 남은 $1$그램짜리 둘로 두 번째 손님의 $1$센트와 $2$센트를 모두 맞출 수 있다.
• 첫 손님이 $1$센트를 쓰면 $1$그램짜리 하나를 준다. 남은 $1$그램짜리 하나와 $2$그램짜리 하나로 두 번째 손님의 $1$센트와 $2$센트를 모두 맞출 수 있다.

첫 손님이 무엇을 고르든 두 번째 손님까지 정확한 무게를 줄 수 있으므로, $k=2$, $C=2$의 답은 $3$이다.

첫째 줄에 테스트 케이스의 수 $T$가 주어진다. 이어지는 $T$개의 줄에 각각 두 정수 $k$와 $C$가 주어진다. $k$는 하루에 오는 손님 수의 최대치이고, $C$는 손님 한 명이 쓸 수 있는 금액의 최대치다.

제한

• $1 \le T \le 100$
• $1 \le k \le 20$
• $1 \le C \le 3$

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 $1$부터 시작하는 테스트 케이스 번호이고, $y$는 매일 아침 주문해야 하는 상자 개수의 최솟값이다.

첫 번째 케이스에서는 $1$그램짜리 하나와 $2$그램짜리 하나를 사면 $1$센트, $2$센트, $3$센트를 모두 맞출 수 있다. 두 번째 케이스에서는 $1$그램짜리 둘과 $2$그램짜리 하나를 사면 된다. 네 번째 케이스에서는 $1$그램짜리 둘, $2$그램짜리 하나, $3$그램짜리 하나로 손님 두 명을 모두 상대할 수 있다.