피자를 좋아하는 성준이는 먹는 것 뿐만 아니라 피자를 예쁘게 커팅하는 것도 좋아한다. 특히 피자의 중심을 지나 지름을 따라 반으로 가를 때에 성준이는 행복을 느낀다. 

 오늘도 친구들과 피자를 먹기로 한 성준이는 피자를 예쁘게 자르려고 한다. 피자는 한 판을 주문했으며 각자 피자를 먹고 싶은 비율을 퍼센트로 제시한다. 성준이는 한 명이 하나의 조각으로 정확히 희망 비율대로 피자를 받을 수 있게 자르려고 한다. 즉, N명의 인원이 총 N개의 조각을 나누어 가지며 각 피자 조각의 넓이는 친구들이 희망한 넓이와 일치해야 한다.

그림 1. 중심을 가르는 커팅선이 두 번 생기는 경우(왼쪽)와 한 번만 생기는 경우(오른쪽)

 예를 들어서 네 명의 인원이 각각 10%, 40%, 40%, 10%의 피자를 먹기로 정했다고 가정해보자. 이 경우 그림 1 처럼 여러가지 방법으로 피자 조각을 나눌 수 있다. 피자 조각의 크기를 배치하는 순서는 자유롭다. 이 때 성준이는 지름을 따라 피자를 자르는 횟수를 최대화 하려고 한다.

 N명의 인원이 나누어 받을 피자의 비율이 입력으로 주어질 때, 지름을 따라 피자를 자를 수 있는 최대 횟수를 계산하는 프로그램을 작성하시오.

입력 형식

 첫 줄에는 테스트케이스의 수를 나타내는 1이상 20이하의 자연수 T가 주어진다. 이후 총 T개의 테스트케이스에 대한 입력이 차레로 주어진다.

 테스트케이스의 첫 줄에는 피자를 나누어 먹을 인원의 수를 나타내는 1이상 8이하의 자연수 N이 주어진다.

 두 번째 줄에는 N명이 각자 피자를 나누어 받을 비율이 공백으로 구분되어 주어진다.

• 모든 비율은 1이상 100이하의 자연수로 주어진다. 
• 비율의 합은 항상 100이다.

출력 형식

 각 테스트케이스에 대한 정답을 차례로 한 줄씩 출력한다.

• 피자를 중심을 지나 지름대로 자를 수 있는 최대 횟수를 출력한다.