최근에, 판다 나라의 금고에서 심각한 보안문제가 발생 했습니다.

금고에는 4개의 숫자를 돌려 맞추는 구식의 좌물쇠를 사용하고 있었는데요, 각각의 숫자는 0부터 9까지 가지고 있으며 다이얼을 위로/아래로 돌려 숫자를 맞추는 형식 입니다. 9에서 위로 돌리면 0이 되고, 0에서 아래로 돌리면 9가 됩니다.

이 금고의 좌물쇠는 4개의 숫자를 이용하므로, 0000 부터 9999 까지 총 10000개의 비밀번호만 가능합니다. 그래서 누구나 10000가지의 숫자만 시도해보면 금고가 열리게 되는거죠.

이런 취약점을 해소하고자, 판다의 보안담당자는 다중 비밀번호 체계를 구축했습니다. 다중 비밀번호 체계는 하나의 비밀번호만 사용하는 대신에 여러개의 비밀번호를 사용합니다. 단, 아래의 규칙을 이용해서 풀어야만 합니다.

• 초기 상태는 0000 입니다.
• 비밀번호를 맞추어야 하는 순서는 정해져 있지 않습니다. 모든 비밀번호를 한번씩 맞춘다음에 UNLOCK 버튼을 누르면 됩니다.
• JUMP 라는 버튼이 있는데, 이 버튼을 누르면 지금까지 맞추었던 어떤 번호든 롤링 없이 한번에 갈 수 있습니다.
• JUMP 버튼을 제외하고 돌리는 횟수를 최소화하여 모든 번호를 맞추어야만 열립니다.
• 만약 돌리는 횟수가 최소횟수를 넘기게 되면 다시 0000이 되고 지금까지 맞추었던 모든 번호는 무효 처리 됩니다.

보안담당자는 이런 시스템이 충분히 안정적일 것이라 합니다. 하지만 최소횟수를 알아내기 위해서는 프로그램을 작성할 필요가 있는데, 판다 나라의 안전을 위해서 최소의 회전수를 구하는 프로그램을 만들어 주세요.

첫 줄에는 테스트 케이스 T (1 <= T <= 10) 이 주어집니다.

각 테스트 케이스에는 첫줄은 자물쇠의 번호키 수 N (1 <= N <= 500) 와, 그 다음에는 4자리 번호(0으로도 시작가능)가 N개 주어집니다.

 각각의 입력에 대해서 모든 번호를 맞출 수 있는 최소 회전수를 출력 해 주세요.

 2번째 테스트 케이스를 설명드리면, 

• 0000 에서 1111 로 : 4 회전
• 1111 에서 1155 로 : 8 회전
• 1155 에서 1111로 점프 : 0 회전 (점프는 이전에 맞추었던 상태로 바로 갈 수 있는 버튼 입니다)
• 1111 에서 5511 로 : 8 회전

따라서 4 + 8 + 8 = 20 이 됩니다.

좌물쇠의 초기 상태가 0000 이지만, JUMP버튼으로 0000으로 갈 수 있지 않고, 맞추어야 하는 비밀번호에 0000 이 있을 때만 갈 수 있습니다.