시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 46 41 36 90.000%

문제

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+XHVjNzc0XHViNTRjLCBcdWNkMWQgXHVjMTJjXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWI3N2MuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjMjE4IFBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IFAgJmxlOyAxMDAwKTxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YmM4OFx1ZDYzOCBUXHVjNjQwIDEyXHVhYzFjXHVjNzU4IFx1Yzc0Y1x1Yzc3NCBcdWM1NDRcdWIyY2MgXHVjODE1XHVjMjE4XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YjYxMFx1ZDU1YywgMTJcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4IFx1YzkxMSBcdWNjYWIgXHVjMjE4XHVjNjQwIFx1YjljOFx1YzljMFx1YjljOSBcdWMyMThcdWIyOTQgXHVkNTZkXHVjMGMxIDBcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWM2NDAgXHVjMTJjXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHVkNTU4XHVjNWVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxMDQzMiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IklzbGFuZHMgaW4gdGhlIERhdGEgU3RyZWFtIiwiZGVzY3JpcHRpb24iOiI8cD5HaXZlbiBhIHNlcXVlbmNlIG9mIGludGVnZXJzIGExLCBhMiwgYTMsIC4uLiwgYW4sIGFuIGlzbGFuZCBpbiB0aGUgc2VxdWVuY2UgaXMgYSBjb250aWd1b3VzIHN1YnNlcXVlbmNlIGZvciB3aGljaCBlYWNoIGVsZW1lbnQgaXMgZ3JlYXRlciB0aGFuIHRoZSBlbGVtZW50cyBpbW1lZGlhdGVseSBiZWZvcmUgYW5kIGFmdGVyIHRoZSBzdWJzZXF1ZW5jZS4gSW4gdGhlIGV4YW1wbGUgYmVsb3csIGVhY2ggaXNsYW5kIGluIHRoZSBzZXF1ZW5jZSBoYXMgYSBicmFja2V0IGJlbG93IGl0LiBUaGUgYnJhY2tldCBmb3IgYW4gaXNsYW5kIGNvbnRhaW5lZCB3aXRoaW4gYW5vdGhlciBpc2xhbmQgaXMgYmVsb3cgdGhlIGJyYWNrZXQgb2YgdGhlIGNvbnRhaW5pbmcgaXNsYW5kLjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXMyXC9pc2xhbmQoMSkucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjI5cHg7IHdpZHRoOjMwMXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0IHRha2VzIGFzIGlucHV0IGEgc2VxdWVuY2Ugb2YgMTIgbm9uLW5lZ2F0aXZlIGludGVnZXJzIGFuZCBvdXRwdXRzIHRoZSBudW1iZXIgb2YgaXNsYW5kcyBpbiB0aGUgc2VxdWVuY2UuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBhIHNpbmdsZSBpbnRlZ2VyIFAsICgxICZsZTsgUCAmbGU7IDEwMDApLCB3aGljaCBpcyB0aGUgbnVtYmVyIG9mIGRhdGEgc2V0cyB0aGF0IGZvbGxvdy4gRWFjaCBkYXRhIHNldCBzaG91bGQgYmUgcHJvY2Vzc2VkIGlkZW50aWNhbGx5IGFuZCBpbmRlcGVuZGVudGx5LjxcL3A+XHJcblxyXG48cD5FYWNoIGRhdGEgc2V0IGNvbnNpc3RzIG9mIGEgc2luZ2xlIGxpbmUgb2YgaW5wdXQuIEl0IGNvbnRhaW5zIHRoZSBkYXRhIHNldCBudW1iZXIsIEsgZm9sbG93ZWQgYnkgMTIgbm9uLW5lZ2F0aXZlIGludGVnZXJzIHNlcGFyYXRlZCBieSBhIHNpbmdsZSBzcGFjZS4gVGhlIGZpcnN0IGFuZCBsYXN0IGludGVnZXJzIGluIHRoZSBzZXF1ZW5jZSB3aWxsIGJlIDAuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggZGF0YSBzZXQgdGhlcmUgaXMgb25lIGxpbmUgb2Ygb3V0cHV0LiBUaGUgc2luZ2xlIG91dHB1dCBsaW5lIGNvbnNpc3RzIG9mIHRoZSBkYXRhIHNldCBudW1iZXIsIEssIGZvbGxvd2VkIGJ5IGEgc2luZ2xlIHNwYWNlIGZvbGxvd2VkIGJ5IHRoZSBudW1iZXIgb2YgaXNsYW5kcyBpbiB0aGUgc2VxdWVuY2UuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d