화학 교사인 영희는 다음 실험 실습을 위해 몇 가지 실험용 액체들을 준비하려고 한다. 실험에는 N가지 기본 물질과 한 종류의 특수 물질이 사용된다. 특수 물질은 서로 다른 세 가지의 기본 물질을 1:1:1로 x 리터씩 총 3x 리터를 혼합하면 특수 물질 x 리터를 얻을 수 있다. 예를 들어서 세 물질 A, B, C를 각각 10리터 씩 혼합하면 10리터의 특수 물질을 얻을 수 있다.

 영희는 다음 수업 시간에 필요한 만큼 실험 재료들을 보충하려고 한다. 학교에 실험 재료를 납품하는 업체는 N가지 기본 물질들을 하나의 세트로 판매하며 한 세트는 모든 기본 물질을 정확히 M 리터씩 포함하고 있다. 단, 특수 물질은 포함하고 있지 않다. 실험에 특수 물질이 필요하다면, 구매한 기본 물질들을 적절히 혼합하여 준비해야 한다. 영희는 모든 기본 물질과 특수 물질을 필요한 만큼 구비할 수 있는 최소한의 수량으로 재료 세트를 구매하려고 한다. 영희를 도와주자.

 예를 들어서 N=4, M=50 일 때 네 개의 기본 물질이 각각 90, 95, 75, 95 리터 씩 필요하고 특수 물질이 10 리터가 필요하다고 해보자. 이 경우 두 세트의 기본 물질을 구매하여 모두 100리터 씩 보충한 후, 10리터의 특수 물질을 기본 물질들로 적절히 합성하여 모든 준비물을 구비할 수 있다. 필요한 양보다 더 많은 물질을 준비하는 것은 상관없다.

그림 1. (N=4, M=50인 위의 예시) 두 세트의 기본 물질을 구매하여 최소 필요 용량을 모두 만족한 예시. 붉은색-초록색-푸른색 물질을 5L씩 혼합하고, 붉은색-푸른색-검정색 물질을 5L씩 혼합하여 특수 물질 총 10L를 구비할 수 있다. 결과적으로 실험에 필요한 최소 용량(각 90, 95, 75, 95, 10 L)을 모두 준비할 수 있다.

 각 기본 물질들과 특수 물질이 다음 실습을 위해 필요한 최소 용량이 입력으로 주어질 때, 구매해야 할 기본 물질 세트의 최소 수량을 계산하는 프로그램을 작성하시오. 필요한 최소 용량보다 더 많은 물질들을 준비하는 것은 상관 없으나, 가능한 적은 수량의 세트를 구매해야 한다.

입력 형식

 첫 줄에는 테스트케이스의 수를 나타내는 1이상 30이하의 자연수 T가 주어진다. 이후 T개의 테스트케이스에 대한 입력이 차례로 주어진다.

 각 테스트케이스의 첫 줄에는 공백으로 구분 된 세 정수 N, M, K가 차례로 주어진다.

• N은 기본 물질의 종류의 수를 나타내는 3이상 20이하의 자연수다.
• M은 물질 세트에 포함된 각 물질의 용량을 나타내는 1이상 1,000이하의 자연수다.
• K는 총 필요한 특수 물질의 용량을 나타내는 0이상 1,000이하의 정수다.

 두 번째 줄에는 공백으로 구분된 N개의 정수가 주어진다.

• 각 정수는 각 물질의 최소 필요 용량을 나타내는 0이상 1,000이하의 정수다.

출력 형식

 각 테스트케이스에 대한 정답을 한 줄에 하나 씩 출력한다.

• 필요한 기본 물질과 특수 물질을 모두 준비하기 위해 구매해야 할 세트의 최소 수량을 출력한다.