아이스 버킷 챌린지

아이스 버킷 챌린지는 근위축성 측삭경화증(ALS) 환자를 돕기 위한 모금 활동이다. 참가자는 다음 두 가지 중 하나를 골라야 한다.

• 얼음물을 몸에 붓고 10바트를 기부한다. 그런 다음 친구 $K$명을 다음 참가자로 지목한다.
• 얼음물을 붓지 않고 100바트를 기부한다. 이때는 아무도 지목하지 못한다.

지목받은 친구도 같은 두 가지 중 하나를 고른다. 지목받은 사람은 모두 참가하고, 규칙을 어기는 사람은 없다. 얼음물을 부으면서 10바트가 아닌 금액을 기부하는 일은 일어나지 않는다.

참가자 한 명에서 시작해 기부금 총액을 $G$바트 이상으로 만들려고 한다. 얼음물을 몸에 붓는 사람이 최소 몇 명이어야 하는지 구하라. $G$는 10의 배수임이 보장된다.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. $T < 100$이다.

다음 $T$개의 줄에 테스트 케이스가 하나씩 주어진다. 각 줄에는 양의 정수 $G$와 $K$가 공백 하나로 구분되어 주어진다. $G \le 10^7$이고 $K < 1000$이다.

각 테스트 케이스마다 얼음물을 몸에 붓는 사람의 최소 인원을 한 줄에 출력한다.

$G = 60$, $K = 10$인 경우 첫 참가자가 100바트를 기부하고 아무도 지목하지 않으면 목표를 넘는다. 얼음물을 붓는 사람은 없다.

$G = 320$, $K = 2$인 경우 첫 참가자가 얼음물을 붓고 10바트를 기부한 뒤 두 명을 지목한다. 지목받은 두 명 중 한 명이 다시 얼음물을 붓고 10바트를 기부한 뒤 두 명을 지목한다. 남은 세 명은 각각 100바트를 기부한다. 총액은 320바트이고 얼음물을 부은 사람은 두 명이다.