고장난 시계

Albert는 n개의 전자 탁상 시계를 가지고 있다. 편의상 시계에는 1, 2, ..., n의 번호가 붙어 있다.

각 시계는 현재 시각을 "HH:MM:SS" 형식으로 시:분:초로 표시하며, 항상 0 ≤ HH < 24, 0 ≤ MM < 60, 0 ≤ SS < 60을 만족한다. HH, MM, SS 값이 10 미만이면 선행 0을 붙여서, 각 시계에는 언제나 6개의 숫자가 표시된다. 예를 들어 "00:00:01"은 자정에서 1초가 지난 시각이고, "12:00:00"은 정오를 나타내며, "18:05:05"는 저녁 6시에서 5분 5초가 지난 시각을 나타낸다.

각 시계가 현재 가리키는 시각은 제각각이고, 고장난 시계도 있어서 매초 1초가 아닌 다른 시간만큼 진행되기도 한다. 구체적으로, i번째 시계가 현재 가리키는 시각을 T[i]라 하고, 이 시계가 매초 D[i]초 이후의 시각을 보여 준다고 하자. 즉, 1초마다 D[i]초씩 증가한다.

예를 들어, n = 3이고 T = [ "11:12:00", "11:12:20", "11:12:40" ], D = [4, 2, 0]이라 하자.

• 현재 각 시계는 다른 시각을 보여 주고 있다.
• 현재로부터 5초가 지난 후, 1번 시계는 "11:12:20", 2번 시계는 "11:12:30", 3번 시계는 "11:12:40"을 보여 준다.
• 현재로부터 10초가 지난 후, 세 시계는 모두 "11:12:40"을 보여 준다. 이때 n개의 시계가 모두 동기화되었다고 한다.
• 현재로부터 43210초가 지난 후, 세 시계는 한 번 더 동기화된다.

이 예제의 경우, 24시간 동안 세 시계는 정확히 두 번 동기화된다.

Albert는 n개의 탁상 시계가 현재 가리키는 시각과 각 시계가 매초 몇 초씩 진행하는지 정보를 이용하여, 앞으로 24시간, 즉 86400초 동안 n개의 시계가 정확히 몇 번 동기화될지 계산하려고 한다. 힌트를 참고하라.

첫 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스는 세 줄에 나누어 주어진다.

테스트 케이스의 첫 줄에는 n이 주어진다.

둘째 줄에는 n개의 시계가 현재 보여 주는 시각 T[i]가 공백으로 구분되어 "HH:MM:SS" 형식의 문자열로 주어진다.

셋째 줄에는 n개의 시계가 매초 몇 초씩 진행하는지 나타내는 D[i]가 공백으로 구분되어 주어진다.

각 테스트 케이스의 정답을 각 줄에 출력한다.

• 1 ≤ T ≤ 20
• 2 ≤ n ≤ 70,000
• T[i]는 언제나 "HH:MM:SS" 형식으로 주어지며 0 ≤ HH < 24, 0 ≤ MM < 60, 0 ≤ SS < 60을 만족한다. HH, MM, SS는 모두 정수이며 10 미만이면 선행 0이 하나 붙어 주어진다.
• -109 ≤ D[i] ≤ 109

이 문제는 임의의 24시간, 즉 86400초 동안 n개의 시계가 동기화되는 횟수를 세면 된다. 현재 시각을 "0초 후"로 보면 0초 후부터 86399초 후까지 n개의 시계가 동기화되는 횟수를 세도 되고(예제 3, 4 참고), 1초 후부터 86400초 후까지 세도 된다. 마찬가지로 s초 후부터 (s+86399)초 후까지 세도 된다. 어떤 방법을 택하더라도 정답은 같다.