14849번 - 동전 교환과 쿼리

구사과 랜드에서 사용하는 동전은 총 4종류이며, c₁, c₂, c₃, c₄원이다. 구사과 랜드에 방문한 욱제는 c₁원 동전 d₁개, c₂원 동전 d₂개, c₃원 동전 d₃개, c₄원 동전 d₄개 있다. 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개의 정수 c₁, c₂, c₃, c₄, q가 주어진다. (1 ≤ c₁ < c₂ < c₃ < c₄ ≤ 1000, 1 ≤ q ≤ 100)

다음 q개의 줄에는 쿼리가 주어진다. 쿼리는 d₁, d₂, d₃, d₄, v로 이루어져 있다. (1 ≤ d₁, d₂, d₃, d₄, v ≤ 10⁵)

각각의 쿼리마다 c₁원 동전 d₁개, c₂원 동전 d₂개, c₃원 동전 d₃개, c₄원 동전 d₄개로 v원을 만드는 방법의 수를 출력한다.