Kem PlanX là một trong những món ăn khoái khẩu của Kaninho và nó được tạo nên từ ba thành phần chính là bơ, sữa và cà phê và trong lúc thưởng thức món kem đặc biệt này, anh ấy đã nảy ra một bài toán và muốn đố các bạn trên lqdoj như sau:

Kaninho sẽ viết công thức của món kem PlanX yêu thích của anh ấy dưới dạng xâu, gồm các ký tự: B(bơ), S (sữa), C (cà phê). Hiện tại Kaninho đang có: \(p_b\) miếng bơ, \(p_s\) miếng sữa và \(p_c\) miếng cà phê ở trong bếp. Ngoài ra, ở bên cạnh nhà anh ta còn có một tạp hoá lớn và cũng đều có các thành phần này, cụ thể giá của các thành phần như sau: \(q_b\) đồng cho \(1\) miếng bơ, \(q_s\) đồng cho \(1\) miếng sữa và \(q_c\) đồng cho \(1\) miếng cà phê.

Bây giờ, Kaninho đang có \(Q\) đồng, hỏi anh ấy có thể tạo ra được tối đa bao nhiêu đĩa kem PlanX. (Biết rằng, các miếng bơ, sữa, cà phê không thể bị bẽ ra hoặc cắt mỏng đi).

Input

• Dòng thứ nhất chứa số \(t(1\le t\le 50)\) - Thể hiện số lượng testcase

• \(t\) block tiếp theo, mỗi block có dạng như sau:

  • Dòng thứ nhất chứa xâu \(S\) gồm các ký tự B,S và C thể hiện công thức của món kem PlanX (độ dài xâu \(S\) không quá 100)

  • Dòng thứ hai chứa \(3\) số nguyên: \(p_b,p_s,p_c\) (\(1\le p_b,p_s,p_c\le 100\))

  • Dòng thứ ba chứa \(3\) số nguyên: \(q_b,q_s,q_c\) (\(1\le q_b,q_s,q_c\le 100\))

  • Dòng thứ tư chứa số nguyên \(Q(1\le Q\le 10^{12})\)

Output

• Ứng với mỗi testcase, in ra số lượng đĩa kem PlanX mà Kaninho có thể tạo ra. (Nếu không thể tạo ra được đĩa kem nào, thì in ra 0)

Example

4
SBC
4 3 4
3 4 3
6
BCCCS
48 14 22
6 14 4
137066
BSCCBBSS
12 17 40
19 12 5
330472
BBCBBCCBB
6 17 35
10 20 7
412693

4
4301
3214
5098