시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 512 MB 21 9 9 69.231%

문제

구사과 랜드에서 사용하는 동전은 총 4종류이며, c1, c2, c3, c4원이다. 구사과 랜드에 방문한 욱제는 c1원 동전 d1개, c2원 동전 d2개, c3원 동전 d3개, c4원 동전 d4개 있다. v원을 만드는 방법의 개수는 총 몇 개 있을지 구하는 프로그램을 작성하시오.

예를 들어, 1원 동전 3개, 2원 동전 2개, 5원 동전 3개, 10원 동전 1개를 가지고 있다면, 10원을 만드는 방법은 총 4가지가 있다.

  • 10 = 1 + 1 + 1 + 2 + 5
  • 10 = 1 + 2 + 2 + 5
  • 10 = 5 + 5
  • 10 = 10

입력

첫째 줄에 테스트 케이스의 개수 T(≤ 100)가 주어진다.

각 테스트 케이스의 첫째 줄에는 5개의 정수 c1, c2, c3, c4, q가 주어진다. (1 ≤ c1 < c2 < c3 < c4 ≤ 1000, 1 ≤ q ≤ 100)

다음 q개의 줄에는 쿼리가 주어진다. 쿼리는 d1, d2, d3, d4, v로 이루어져 있다. (1 ≤ d1, d2, d3, d4, v ≤ 105)

출력

각각의 쿼리마다 c1원 동전 d1개, c2원 동전 d2개, c3원 동전 d3개, c4원 동전 d4개로 v원을 만드는 방법의 수를 출력한다.

예제 입력 1

2
1 2 5 10 2
3 2 3 1 10
1000 2 2 2 900
10 20 30 40 1
100 100 100 100 101

예제 출력 1

4
27
0

출처