시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 44 39 34 89.474%

문제

n개의 정수 수열 a1, a2, a3, ..., an에 대해, 섬이란 다음 조건을 만족하는 연속된 부분수열을 말한다.

  • 섬의 모든 수는 부분수열이 시작하기 직전 수보다 크다.
  • 섬의 모든 수는 부분수열이 끝난 직후의 수보다 크다.

아래의 예시에는 각각의 예제 수열에 대한 모든 섬이 표시되어 있다.

이 문제에서 수열은 항상 12개의 음이 아닌 정수로 이루어져 있다.

이 때, 총 섬의 개수를 출력하라.

입력

첫 줄에 테스트 케이스의 수 P가 주어진다. (1 ≤ P ≤ 1000)

각 테스트 케이스는 테스트 케이스의 번호 T와 12개의 음이 아닌 정수로 이루어져 있다. 또한, 12개의 정수 중 첫 수와 마지막 수는 항상 0이다.

출력

각 테스트 케이스마다 테스트 케이스의 번호와 섬의 수를 공백으로 구분하여 출력한다.

예제 입력 1

4
1 0 0 1 1 2 2 1 1 0 1 2 0
2 0 1 2 4 3 1 3 4 5 2 1 0
3 0 1 2 4 4 1 0 2 4 1 0 0
4 0 1 2 3 4 5 6 7 8 9 10 0

예제 출력 1

1 4
2 8
3 6
4 10

힌트

W3sicHJvYmxlbV9pZCI6IjEwNDMyIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHViMzcwXHVjNzc0XHVkMTMwIFx1YzJhNFx1ZDJiOFx1YjliY1x1Yzc1OCBcdWMxMmMiLCJkZXNjcmlwdGlvbiI6IjxwPm5cdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4IFx1YzIxOFx1YzVmNCBhMSwgYTIsIGEzLCAuLi4sIGFuXHVjNWQwIFx1YjMwMFx1ZDU3NCwgXHVjMTJjXHVjNzc0XHViNzgwIFx1YjJlNFx1Yzc0YyBcdWM4NzBcdWFjNzRcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0IFx1YzVmMFx1YzE4ZFx1YjQxYyBcdWJkODBcdWJkODRcdWMyMThcdWM1ZjRcdWM3NDQgXHViOWQwXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1YzEyY1x1Yzc1OCBcdWJhYThcdWI0ZTAgXHVjMjE4XHViMjk0IFx1YmQ4MFx1YmQ4NFx1YzIxOFx1YzVmNFx1Yzc3NCBcdWMyZGNcdWM3OTFcdWQ1NThcdWFlMzAgXHVjOWMxXHVjODA0IFx1YzIxOFx1YmNmNFx1YjJlNCBcdWQwNmNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YzEyY1x1Yzc1OCBcdWJhYThcdWI0ZTAgXHVjMjE4XHViMjk0IFx1YmQ4MFx1YmQ4NFx1YzIxOFx1YzVmNFx1Yzc3NCBcdWIwNWRcdWIwOWMgXHVjOWMxXHVkNmM0XHVjNzU4IFx1YzIxOFx1YmNmNFx1YjJlNCBcdWQwNmNcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHVjNTQ0XHViNzk4XHVjNzU4IFx1YzYwOFx1YzJkY1x1YzVkMFx1YjI5NCBcdWFjMDFcdWFjMDFcdWM3NTggXHVjNjA4XHVjODFjIFx1YzIxOFx1YzVmNFx1YzVkMCBcdWIzMDBcdWQ1NWMgXHViYWE4XHViNGUwIFx1YzEyY1x1Yzc3NCBcdWQ0NWNcdWMyZGNcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIHNyYz1cImh0dHBzOlwvXC93d3cuYWNtaWNwYy5uZXRcL3VwbG9hZFwvaW1hZ2VzMlwvaXNsYW5kKDEpLnBuZ1wiIFwvPjxcL3A+XHJcblxyXG48cD5cdWM3NzQgXHViYjM4XHVjODFjXHVjNWQwXHVjMTFjIFx1YzIxOFx1YzVmNFx1Yzc0MCBcdWQ1NmRcdWMwYzEgMTJcdWFjMWNcdWM3NTggXHVjNzRjXHVjNzc0IFx1YzU0NFx1YjJjYyBcdWM4MTVcdWMyMThcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0IFx1YjU0YywgXHVjZDFkIFx1YzEyY1x1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHViNzdjLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YzIxOCBQXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBQICZsZTsgMTAwMCk8XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWJjODhcdWQ2MzggVFx1YzY0MCAxMlx1YWMxY1x1Yzc1OCBcdWM3NGNcdWM3NzQgXHVjNTQ0XHViMmNjIFx1YzgxNVx1YzIxOFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWI2MTBcdWQ1NWMsIDEyXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOCBcdWM5MTEgXHVjY2FiIFx1YzIxOFx1YzY0MCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjMjE4XHViMjk0IFx1ZDU2ZFx1YzBjMSAwXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHViYzg4XHVkNjM4XHVjNjQwIFx1YzEyY1x1Yzc1OCBcdWMyMThcdWI5N2MgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1ZDU1OFx1YzVlYyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTA0MzIiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJJc2xhbmRzIGluIHRoZSBEYXRhIFN0cmVhbSIsImRlc2NyaXB0aW9uIjoiPHA+R2l2ZW4gYSBzZXF1ZW5jZSBvZiBpbnRlZ2VycyBhMSwgYTIsIGEzLCAuLi4sIGFuLCBhbiBpc2xhbmQgaW4gdGhlIHNlcXVlbmNlIGlzIGEgY29udGlndW91cyBzdWJzZXF1ZW5jZSBmb3Igd2hpY2ggZWFjaCBlbGVtZW50IGlzIGdyZWF0ZXIgdGhhbiB0aGUgZWxlbWVudHMgaW1tZWRpYXRlbHkgYmVmb3JlIGFuZCBhZnRlciB0aGUgc3Vic2VxdWVuY2UuIEluIHRoZSBleGFtcGxlIGJlbG93LCBlYWNoIGlzbGFuZCBpbiB0aGUgc2VxdWVuY2UgaGFzIGEgYnJhY2tldCBiZWxvdyBpdC4gVGhlIGJyYWNrZXQgZm9yIGFuIGlzbGFuZCBjb250YWluZWQgd2l0aGluIGFub3RoZXIgaXNsYW5kIGlzIGJlbG93IHRoZSBicmFja2V0IG9mIHRoZSBjb250YWluaW5nIGlzbGFuZC48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzMlwvaXNsYW5kKDEpLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjIyOXB4OyB3aWR0aDozMDFweFwiIFwvPjxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCB0YWtlcyBhcyBpbnB1dCBhIHNlcXVlbmNlIG9mIDEyIG5vbi1uZWdhdGl2ZSBpbnRlZ2VycyBhbmQgb3V0cHV0cyB0aGUgbnVtYmVyIG9mIGlzbGFuZHMgaW4gdGhlIHNlcXVlbmNlLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgYSBzaW5nbGUgaW50ZWdlciBQLCAoMSAmbGU7IFAgJmxlOyAxMDAwKSwgd2hpY2ggaXMgdGhlIG51bWJlciBvZiBkYXRhIHNldHMgdGhhdCBmb2xsb3cuIEVhY2ggZGF0YSBzZXQgc2hvdWxkIGJlIHByb2Nlc3NlZCBpZGVudGljYWxseSBhbmQgaW5kZXBlbmRlbnRseS48XC9wPlxyXG5cclxuPHA+RWFjaCBkYXRhIHNldCBjb25zaXN0cyBvZiBhIHNpbmdsZSBsaW5lIG9mIGlucHV0LiBJdCBjb250YWlucyB0aGUgZGF0YSBzZXQgbnVtYmVyLCBLIGZvbGxvd2VkIGJ5IDEyIG5vbi1uZWdhdGl2ZSBpbnRlZ2VycyBzZXBhcmF0ZWQgYnkgYSBzaW5nbGUgc3BhY2UuIFRoZSBmaXJzdCBhbmQgbGFzdCBpbnRlZ2VycyBpbiB0aGUgc2VxdWVuY2Ugd2lsbCBiZSAwLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIGRhdGEgc2V0IHRoZXJlIGlzIG9uZSBsaW5lIG9mIG91dHB1dC4gVGhlIHNpbmdsZSBvdXRwdXQgbGluZSBjb25zaXN0cyBvZiB0aGUgZGF0YSBzZXQgbnVtYmVyLCBLLCBmb2xsb3dlZCBieSBhIHNpbmdsZSBzcGFjZSBmb2xsb3dlZCBieSB0aGUgbnVtYmVyIG9mIGlzbGFuZHMgaW4gdGhlIHNlcXVlbmNlLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==