ห้างสรรพสินค้าแห่งหนึ่ง มีนโยบายลดการใช้ถุงพลาสติกโดยมุ่งเน้นให้ลูกค้าใช้ถุงผ้าในการจับจ่ายใช้สอยเพื่อ ลดปริมาณขยะ แต่อย่างไรก็ตามยังคงมีลูกค้าจ านวนหนึ่งที่ยังคงไม่น าถุงผ้ามาซื้อของ ณ ห้างสรรพสินค้าแห่งนี้ จาก ปัญหาดังกล่าว ทีมผู้บริหารห้างสรรพสินค้าดังกล่าว จึงมีนโยบายที่จะแก้ปัญหาดังกล่าว โดยท าการก าหนดเงื่อนไข ส าหรับการแจกถุงพลาสติกให้แก่ลูกค้าตามจ านวนเงินที่ลูกค้าซื้อสินค้า ถุงพลาสติกที่จะท าการแจกมี 3 ขนาดและ รองรับน้ าหนักได้ต่างกันดังนี</p>

1. ถุงพลาสติกขนาดเล็ก จะสามารถรองรับน้ าหนักได้ 500 กรัม
2. ถุงพลาสติกขนาดกลาง จะสามารถรองรับน้ าหนักได้ 1,250 กรัม
3. ถุงพลาสติกขนาดใหญ่ จะสามารถรองรับน้ าหนักได้ 2,000 กรัม

โดยห้างสรรพสินค้านี้จะท าการแจกถุงพลาสติกแก่ลูกค้า โดยมีเงื่อนไขว่าดังต่อไปนี้

1. เมื่อลูกค้าซื้อสินค้าในราคารวมทั้งหมดน้อยกว่า 500 บาท จะได้รับถุงพลาสติกขนาดเล็ก 1 ถุง
2. เมื่อลูกค้าซื้อสินค้าในราคารวมทั้งหมดมากกว่าเท่ากับ 500 บาทแต่น้อยกว่าหรือเท่ากับ 1,000 บาทจะได้รับ ถุงพลาสติกขนาดกลาง 1 ถุง
3. เมื่อลูกค้าซื้อสินค้าในราคารวมทั้งหมดมากกว่าเท่ากับ 1,000 บาท จะได้รับถุงพลาสติกขนาดใหญ่ 1 ถุง
4. ถ้าลูกค้าซื้อสินค้าชิ้นหนึ่งๆที่มีน้ าหนักมากกว่า 2,000 กรัม ลูกค้าจะต้องถือสินค้าชนิดนั้นๆกลับบ้านเองโดย ไม่ท าการใส่ถุงพลาสติก (เพราะไม่มีถุงขนาดใดรองรับน้ าหนักได้)

จากเงื่อนไขดังกล่าว ถ้าลูกค้าต้องการถุงพลาสติกเพื่อใส่ของมากเกินกว่าที่ห้างสรรพสินค้าแจกให้ก าหนด ลูกค้า จะต้องท าการซื้อถุงพลาสติกจากห้างสรรพสินค้า โดยถุงพลาสติกขนาดเล็ก กลาง และ ใหญ่ จะถูกขายในราคา 5, 12 และ 20 บาท ตามล าดับ

จากการขายถุงพลาสติกดังกล่าว จงท าการเขียนโปรแกรมเพื่อช่วยลูกค้าที่จะท าให้พวกเขาจะสามารถจ่ายเงินค่า ถุงพลาสติกได้น้อยที่สุดเพื่อที่จะใส่สินค้าที่หนักไม่เกิน 2,000 กรัม ได้ทั้งหมด

입력 형식

บรรทัดแรก ระบุจ านวนเต็ม T (1 ≤ T ≤ 100) แทนจ านวนข้อมูลทดสอบ จากนั้นในแต่ละชุดข้อมูลทดสอบ รูปแบบข้อมูลดังนี้</p>

• บรรทัดแรกของชุดข้อมูลทดสอบจะระบุจ านวนเต็ม N (1 ≤ N ≤ 10) ที่แสดงถึงจ านวนชนิดสินค้าที่ลูกค้า ท าการซื้อจากห้างสรรพสินค้า
• อีก N บรรทัดต่อมาจะประกอบไปด้วยข้อมูลจ านวนเต็ม 3 จ านวน ซึ่งก็คือ A B และ C ตามล าดับ โดย A จะ หมายถึง ราคาต่อ 1 หน่วยสินค้า B จะหมายถึงจ านวนสินค้าที่ถูกซื้อ และ C จะหมายถึง น้ าหนักของสินค้า แต่ละชิ้น (หน่วยเป็นกรัม) ตามล าดับ (1 ≤ A ≤ 1000000; 1 ≤ B ≤ 2; 1 ≤ C ≤ 100000)

มีทั้งสิ้น T บรรทัด โดยข้อมูลแต่ละบรรทัดจะประกอบไปด้วยเลขจ านวนเต็ม 1 จ านวนที่ซึ่งแสดงถึงจ านวนเงินที่น้อย ที่สุดที่ลูกค้าต้องท าการจ่ายในการซื้อถุงพลาสติกเพื่อใช้ใส่ของกลับบ้าน

예제 입력

2
3
700 2 1000
600 1 750
300 1 250
4
300 1 330
200 1 250
100 1 300
20 1 500

예제 출력

12
5