eolymp
bolt
Try our new interface for solving problems
Problems

Islands in the Data Stream

Islands in the Data Stream

Time limit 1 second
Memory limit 128 MiB

Given a sequence of integers a_1, a_2, a_3, ..., a_n, an island in the sequence is a contiguous subsequence for which each element is greater than the elements immediately before and after the subsequence. In the examples below, each island in the sequence has a bracket below it. The bracket for an island contained within another island is below the bracket of the containing island.

Write a program that takes as input a sequence of 15 non-negative integers, in which each integer differs from the previous integer by at most 1, and outputs the number of islands in the sequence.

Input data

The first line contains the number of data sets p~(1 \le p \le 1000) that follow. Each data set should be processed identically and independently.

Each data set consists of a single line. It contains the data set number k, followed by 15 non-negative integers separated by a single space. The first and last integers in the sequence will be 0. Each integer will differ from the previous integer by at most 1.

Output data

For each data set print a line that consists of the data set number k, followed by a single space followed by the number of islands in the sequence.

Examples

Input example #1
4
1 0 0 1 1 2 2 1 1 0 1 2 2 1 1 0
2 0 1 2 3 4 3 2 1 2 3 4 3 2 1 0
3 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
4 0 1 2 3 4 5 6 7 6 5 4 3 2 1 0
Output example #1
1 4
2 7
3 7
4 7
Source 2013 ACM Greater New York Region, October 27, Problem A