Description
예준이는 요즘 밀가루 공장에서 밀가루를 배달하고 있다. 예준이는 지금 빵가게에 밀가루를 정확하게 N킬로그램을 납품해야 한다. 밀가루 공장에서 만드는 밀가루는 포대에 담겨져 있다. 포대는 1킬로그램, 3킬로그램, 7킬로그램, 12킬로그램의 4가지가 있다.
예준이는 귀찮기 때문에, 최대한 적은 갯수의 포대를 차에 싣고 가려고 한다. 예를 들어, 18킬로그램 밀가루를 배달해야 할 때, 3킬로그램 포대 6개를 가져가도 되지만, 12킬로그램 1개, 3킬로그램 2개를 배달하면 더 적은 개수의 봉지를 배달할 수 있다.
예준이가 밀가루를 정확하게 N킬로그램 배달해야 할 때, 포대 몇 개를 가져가면 되는지 그 최소 갯수를 구하는 프로그램을 작성하시오.
Input
첫 줄에 테스트케이스의 개수(t)가 입력된다.( 1 <= t <= 20 )
다음 줄 부터 배달해야 할 밀가루의 무게값 N이 한 줄에 하나씩 t줄 입력된다.(1 <= N <= 10,000)
Output
각 테스트케이스에 대하여 예준이가 배달해야 할 밀가루의 최소 포대수를 한 줄에 하나씩 출력한다.