Giải bài trực tuyến

Yến là một cô gái xinh đẹp, giỏi giang nên được rất nhiều chàng trai để ý. Yến giờ đã đủ 18 tuổi, theo khoản 1, điều 9 luật hôn nhân và gia đình là đã đủ tuổi kết hôn. Tuần trước, có chàng trai một chàng trai tên X đến hỏi cưới, Yến soi chàng X rất kĩ và thấy cũng ... ổn. Suy nghĩ một hồi lâu: "Vàng giờ giá đang cao, Việt Nam Đồng thì mất giá. Euro thì sao nhỉ? Đang khủng hoảng nợ công ở châu Âu nên xem ra cũng không an toàn. Bảng Anh có vẻ ổn. Nhưng chả biết được vài năm nữa giá cả thay đổi thế nào" Vậy là Yến quyết định đưa ra lời thách cưới sau khi cân nhắc: "A ngàn Bảng Anh, D triệu Việt Nam Đồng, E ngàn Euro, M ngàn Đô la Mỹ, T ngàn Nhân dân Tệ và V cây Vàng".

Chàng X kiểm tra lại tài khoản thì thấy mình có a ngàn bảng Anh, d triệu Việt Nam Đồng, e ngàn Euro, m ngàn Đô la Mỹ, t ngàn Nhân dân Tệ và v cây Vàng. May mắn cho chàng, có một ngân hàng cho phép đổi theo một số tỉ lệ dạng: A1 D1 E1 M1 T1 V1 thành A2 D2 E2 M2 T2 V2 (chỉ cho phép đổi một chiều, không có chiều ngược lại). Ví dụ:

• 5 0 0 0 0 0 -> 0 1 1 1 1 1
• 0 0 0 0 0 1 -> 1 0 0 0 0 0

Nếu ban đầu chàng X có 4 0 0 0 0 thì sẽ không đủ để thực hiện việc đổi theo 1 trong 2 tỉ lệ trên. Nhưng ngân hàng châm chước có thể cho chàng vay tạm, miễn là sau cùng chàng không nợ nần gì ngân hàng. Ví dụ thực hiện mua bán theo tỉ lệ 1, chàng X sẽ còn -1 1 1 1 1 1 rồi thực hiện tiếp mua bán theo tỉ lệ 2 sẽ có 0 1 1 1 1 0. (không còn nợ nần gì ngân hàng)

Sau khi hoàn đổi tiền xong, chàng X sẽ đem lễ vật theo đúng yêu cầu đến cầu hôn. Bạn hãy giúp chàng X tính xem cần ít nhất bao nhiêu lần đổi tiền để có thể có đủ lễ vật rước nàng về dinh.

Input

Dòng đầu tiên ghi số T là số test (1 <= T <= 10). Mỗi test được ghi theo định dạng sau:

• Dòng đầu ghi 6 số A D E M T V. (0 <= A D E M T V <= 50)
• Dòng thứ hai ghi 6 số a d e m t v. (0 <= a d e m t v <= 50)
• Dòng thứ ba ghi số N là số các phương án đổi tiền ngân hàng cho phép. (0 <= N <= 3)
• Tiếp theo là N dòng, mỗi dòng ghi 12 số theo dạng A1 D1 E1 M1 T1 V1 A2 D2 E2 M2 T2 V2. (0 <= A1 D1 E1 M1 T1 V1 A2 D2 E2 M2 T2 V2 <= 10) 

Output

Ghi ra duy nhất một số là số lần đổi tiền ít nhất. Nếu không có cách đổi thì in ra :(

Example

Input:
3

0 1 0 0 1 0 

4 0 0 0 0 0

2

5 0 0 0 0 0 0 1 1 1 1 1

0 0 0 0 0 1 1 0 0 0 0 0

8 0 0 0 0 0

0 0 0 0 0 9

1

0 0 0 0 0 5 5 0 0 0 0 0

0 0 0 0 0 10

10 0 0 0 0 0

1

1 0 0 0 0 0 0 0 0 0 0 1
Output:
2

:(

10