Rummy Score

Interview

Time limit1sMemory limit1024 MB

Summary

Given seven cards per hand, find the minimum sum of card values left outside groups of three or more cards with equal or consecutive values.

Level: Medium4 of 10
Topics: Backtracking, Brute force
Solved: No attempts yet

Problem

Mack and Zack, the twins of Dr. Orooji, play Rummy with a modified deck. Card values run from 1 to 13. The card 1 is only 1, not both 1 and 14. Cards have no suits. A deck may contain any number of cards of each value, unlike a standard deck that has exactly four of each.

You are given the seven cards in a Rummy hand held by Mack or Zack. Find the points lost by the hand.

In Rummy, a group is three or more cards with the same value or with consecutive values. Examples are {4, 4, 4}, {6, 6, 6, 6, 6}, {9, 10, 11}, and {1, 2, 3, 4}. The points lost by a hand is the sum of the values of the cards that belong to no group. Group the cards so that this sum is as small as possible. A card can be used in only one group. For example, in the hand {2, 2, 2, 3, 4, 8, 10}, the grouping {2, 3, 4} is better than {2, 2, 2}. The hand cannot form both {2, 2, 2} and {2, 3, 4}, because it has only three cards of value 2.

Input

The first line contains a positive integer n, the number of hands. Each of the next n lines contains seven integers from 1 to 13, separated by single spaces.

Output

For each hand, print "Rummy Hand: v", where v is the input values exactly as given. On the next line, print the points lost by the hand. Print a blank line after each test case.

Examples1

Example 1

Input

7
5 2 2 6 2 10 4
11 11 11 11 1 2 3
11 2 3 4 5 13 1
4 5 6 6 6 6 13
2 2 2 3 4 8 10
12 13 1 4 4 4 4
10 10 10 8 9 8 9

Expected output

Rummy Hand: 5 2 2 6 2 10 4
10

Rummy Hand: 11 11 11 11 1 2 3
0

Rummy Hand: 11 2 3 4 5 13 1
24

Rummy Hand: 4 5 6 6 6 6 13
13

Rummy Hand: 2 2 2 3 4 8 10
22

Rummy Hand: 12 13 1 4 4 4 4
26

Rummy Hand: 10 10 10 8 9 8 9
10