## Practices 06

Note there is an output-reduced version of practices 06: Assignment in brute

## Recursion

import time
# practices 06

# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
# # --------------------------------------------------------------------- # #
# #                         C A U T I O N                                 # #
# # --------------------------------------------------------------------- # #
# #                                                                       # #
# #  In this set of practices, we provide not only problem descriptions,  # #
# #  but also quite detailed descriptions of solution IMPLEMENTATIONS.    # #
# #  So, the problems are nearly completely solved for you.   :-)         # #
# #  See sections Solution strategy and Solution Implementation           # #
# #  following each task description.                                     # #
# #                                                                       # #
# #  The presented problems may be solved in many different ways.         # #
# #  However, the correct result of your program depends on your code     # #
# #  closely following the implementation description.                    # #
# #                                                                       # #
# #  The output of the code is the number of recursive calls              # #
# #  of a function which solves a problem, and that should coincide       # #
# #  with the output produced by the described function.                  # #
# #  For that reason we provide a little bit more examples than usualy.   # #
# #  If your code repeatedly fails to recreate them exactly,              # #
# #  ask the teacher for more examples/hints/assistance etc.              # #
# #                                                                       # #
# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #

# Common input format
# -------------------
# All tasks in practices 06 set share common data input format:
# The first line contains the number of the task (1 - 5).
# The second line contains the number N of lists in the input.
# Next, there are N lines of input, each contains one input list.
# Meaning of the values in the input list is specified in detail in each task.
# Each list consists only of integers. List entries are separated by single space,
# there are no other symbols on the input line.
# The input always contain exactly one data set of one task.
# In the evaluation system, the code is run repeatedly, each time with different input
# from which the running program reads the data.

# Solution code structure
# -----------------------
# The code reads the input data, including the number of the task.
# Next, it runs a function or a block of code which accepts the input data
# and computes and prints the solution to it.
# It is recommended to wrap the solution of each task in a separate function,
# an example (not obligatory!) structure of the code
# is illustrated by the contents of this file.

# ================================================================================

# ------------------------------------------------------------------------------

pass
'''
------------------------------------------------------------------
------------------------------------------------------------------
A string is made of two characters, 'o' and 'I'.
Let us call them tiny character and huge character.
Two non-negative integers N and K are given, K <= N.
The task is to generate a list S of all strings
which length is N and which contain exactly K huge characters.

------------------------------------------------------------------
Input and Output
------------------------------------------------------------------
Input
The first input line contains single integer 1, it is the number of the task.
The second line contains single integer C, the number of cases.
Next, there are C lines, each represents one case.
Each line contains values N and K, separated by space.
It holds, 1 <= N <= K <= 20.

Output
For each input case, the output contains one line with the length of list S
and the number of calls of the recursive function which generated the list.

------------------------------------------------------------------
Examples
------------------------------------------------------------------
Input
1
1
3 1
Output
3 5
# S = Ioo oIo ooI
( The contents of S is not part of the output, it is listed here for
( reference only. Brackets, commas, and quotes in S specification are omitted.)
# ----------------------------------------------------------------
Input
1
1
4 1
Output
4 7
# S = Iooo oIoo ooIo oooI
# ----------------------------------------------------------------
Input
1
1
4 2
Output
6 11
# S = IIoo IoIo IooI oIIo oIoI ooII
# ----------------------------------------------------------------
Input
1
1
5 3
Output
10 19
# S = IIIoo IIoIo IIooI IoIIo IoIoI IooII oIIIo oIIoI oIoII ooIII
# ----------------------------------------------------------------
Input
1
3
7 0
7 1
7 4
Output
1 1
7 13
35 69
# The corresponding lists are
# S = ooooooo
# S = Ioooooo oIooooo ooIoooo oooIooo ooooIoo oooooIo ooooooI
# S = IIIIooo IIIoIoo IIIooIo IIIoooI IIoIIoo IIoIoIo IIoIooI IIooIIo IIooIoI IIoooII
IoIIIoo IoIIoIo IoIIooI IoIoIIo IoIoIoI IoIooII IooIIIo IooIIoI IooIoII IoooIII
oIIIIoo oIIIoIo oIIIooI oIIoIIo oIIoIoI oIIooII oIoIIIo oIoIIoI oIoIoII oIooIII
ooIIIIo ooIIIoI ooIIoII ooIoIII oooIIII

------------------------------------------------------------------
Solution strategy
------------------------------------------------------------------
The solution is based on the recursive idea which works generally,
we demonstrate it here on some particular values for better
intuitive illustration:

Let us suppose, N = 5, K = 3.
To generate the list of all strings of length 5, with 3 huge characters,
Let us suppose we already have at our hands two lists L1 and L2:
L1 contains all strings of length 4 with 2 huge characters.
L2 contains all strings of length 4 with 3 huge characters.

L1 = IIoo IoIo IooI oIIo oIoI ooII
L2 = IIIo IIoI IoII oIII

Now, we prepend  one huge character to each string in L1.
In this way we obtain all strings of length 5, with 3 huge characters,
which begin with huge character

Next, we prepend  one tiny character to each string in L2.
In this way we obtain all strings of length 5, with 3 huge characters,
which begin with tiny character.

L1 = IIIoo IIoIo IIooI IoIIo IoIoI IooII
L2 = oIIIo oIIoI oIoII ooIII

Finally, we just merge L1 and L2 into a single list, because
now we have all demanded strings of length 5.

To obtain a general solution, we just substitute N for 5, N-1 for 4,
K for 3, and K-1 for 2 in the description above.

-----
Another solution strategy example:
Let us suppose N = 4, K = 2.

First, let recursive calls generate two lists:
L1 contains all strings of length 3 with 1 huge character.
L2 contains all strings of length 3 with 2 huge characters.

L1 = Ioo oIo ooI
L2 = IIo IoI oII

Next,  after prepending huge character to strings in L1 and
tiny character to each string in L2 we obtain:

L1 = IIoo IoIo IooI
L2 = oIIo oIoI ooII

Finally, L1 + L2 is the solution for N=4, K=2.
------------------------------------------------------------------
Solution implementation
------------------------------------------------------------------
Recursive function F

Parameters of F are N and K.

First, F checks if it is time to stop and return from recursion.
If K is equal to 0, F immediately returns string consisting of N tiny characters.
If K is equal to N, F immediately returns string consisting of N huge characters.

When neither of the previous cases happens, F performs two recursive calls
and returns the combined result of both calls.
The first call returns list L1 of all strings,
which Length is N-1 and which contain K-1 huge characters.
The second call returns list L2 of all strings,
which Length is N-1 and which contain K huge characters.
Now, the function prepends each string in L1 with huge character
and each string in L2 with tiny character.
Finally, it returns the concatenation of L1 and  L2.

Clearly, when constructing the solution for the original input values N and K,
the recursive function F has to be called two times -- with parameter C set to
tiny character in one call and parameter C set to huge character in the other call.
The resulting two lists returned from both calls have to be marged into single one
to obtain correctly the all strings which represent the solution of the problem.

------------------------------------------------------------------
'''

# ------------------------------------------------------------------------------

pass

'''
------------------------------------------------------------------
------------------------------------------------------------------
A string is made of two characters, 'o' and 'I'.
Let us call them tiny character and huge character.
Two non-negative integers N and K are given, K <= N.
The task is to generate a list of all strings
which length is N and which contain exactly K huge characters.
The additional condition says that there should not occur
two immediately adjacent huge characters anywhere in all generated strings.

------------------------------------------------------------------
Input and Output
------------------------------------------------------------------
Input
The first input line contains single integer 2, it is the number of the task.
The second line contains single integer C, the number of cases.
Next, there are C lines, each represents one case.
Each line contains values N and K, separated by space.
It holds, 1 <= N <= K <= 20.

Output
For each input case, the output contains one line with the length of list S
and the number of calls of the recursive function which generated the list.

------------------------------------------------------------------
Examples
------------------------------------------------------------------
Input
2
1
3 1
Output
3 5
# S = Ioo oIo ooI
( The contents of S is not part of the output, it is listed here for
( reference only. Brackets, commas, and quotes in S specification are omitted.)
# ----------------------------------------------------------------
Input
4 1
Output
4 18
# S = Iooo oIoo ooIo oooI
# ----------------------------------------------------------------
Input
4 2
Output
3 18
# S = IoIo IooI oIoI
# ----------------------------------------------------------------
Input
5 3
Output
1 31
# S = IoIoI
# ----------------------------------------------------------------
Input
2
4
4 3
3 2
8 4
10 4
Output
0 18
1 10
5 141
35 374
# The corresponding lists are
# S is empty
# S = IoI
# S = 'IooIoIoI IoIooIoI IoIoIooI IoIoIoIo oIoIoIoI
# S = IooooIoIoI IoooIooIoI IoooIoIooI IoooIoIoIo IooIoooIoI IooIooIooI IooIooIoIo
IooIoIoooI IooIoIooIo IooIoIoIoo IoIooooIoI IoIoooIooI IoIoooIoIo IoIooIoooI
IoIooIooIo IoIooIoIoo IoIoIooooI IoIoIoooIo IoIoIooIoo IoIoIoIooo oooIoIoIoI
ooIooIoIoI ooIoIooIoI ooIoIoIooI ooIoIoIoIo oIoooIoIoI oIooIooIoI oIooIoIooI
oIooIoIoIo oIoIoooIoI oIoIooIooI oIoIooIoIo oIoIoIoooI oIoIoIooIo oIoIoIoIoo

------------------------------------------------------------------
Solution strategy
------------------------------------------------------------------
The solution is based on the recusive idea:

The parameters of recursive function F will be the values of N and K,
and also the character C which will appear as the first character
of all strings generated by F.

If the parameter N is bigger than 1, F will call itself recursively
to obtain the list of all demanded strings of length N-1.
Then, it will prepend all those strings by the C character
and return the updated list.

However, the detailed behaviour of F will depend on the C parameter.

If C is huge character, and it will appear as the first character of all
returned strings, then the second character in all those strings must be
tiny character and thus, the recursive call inside F must
specify that all strings generated by the recursive call should start
with tiny character.
On the other hand, if C is tiny character, it can be prepended to any string.
In this case, F will call itself recursively twice, each time
with different demanded first character in the strings returned by the recursive call.
Also, the parameter K has to be specified in all recursive calls
accordingly, as the example below demonstrates.

For example, let N, K, C = 5, 2, hugeCharacter.
Then, F will call recursively itself with
parameters (N-1, K-1, tinyCharacter) = (4, 1, tinyCharacter)
and that call will return strings oIoo, ooIo, oooI.
F will prepend each of those strings by I and return
(list of) strings IoIoo, IooIo, IoooI.

To continue the example, let N, K, C = 5, 2, tinyCharacter.
Then, F will call recursively itself with
parameters (N-1, K, hugeCharacter) = (4, 2, hugeCharacter)
and that call will return strings IoIo, IooI.
F will prepend each of those strings by o and return
(list of) strings oIooI, oIoIo.
Then, F will perform another recursive call with
parameters (N-1, K, tinyCharacter) =  (4, 2, tinyCharacter)
and that call will return string oIoI.

Finally, F will merge all strings into a single list
containing oIoI, IooI, IoIo, and prepend each string with o,
and return  (list of) strings ooIoI, oIooI, oIoIo.

Note that the two described calculations, with parameters
(N, K, C) = (5, 2, hugeCharacter) and (N, K, C) = (5, 2, tinyCharacter)
together form a solution of the task of generating all strings
of length 5 with 2 huge characters in them.

------------------------------------------------------------------
Solution implementation
------------------------------------------------------------------
Recursive function F

Parameters of F are N, K, and C which is the first character of all returned strings.

First, F verifies if it is time to stop and return from recursion.
That happens only when N equals to 1. In that case, two specific checks are done:
1. If K is 1 and C is huge character then a list with a single string is returned,
the string contains only one character - C.
2. If K is 0 and C is tiny character then a list with a single string is returned,
the string contains only one character - C.
If none of the conditions 1 or 2 holds, F returns empty list.

The following part of F is performed when N > 1.

If C is huge character, F is called recursively with both parameters N and K
decreased by 1 and C equal to tiny character.
In the list obtained by the recursive call, each string is prepended with
huge character and this modified list is returned as a result of F.

If C is tiny character, two recursive calls are done.
In both calls, N is decreased by 1, K is unchanged. One of the calls takes as its third
parameter tiny character and the other call takes as its third parameter huge character.
The lists returned from both calls are concatenated into a single list.
Each string in the concatenated list is prepended by tiny character.
Finally, the modified list is returned as the result of F.

------------------------------------------------------------------
'''

# ------------------------------------------------------------------------------

pass

'''
------------------------------------------------------------------
------------------------------------------------------------------
We are given a list L of integers, some of them positive, some of them negative,
there may be also some zeros in the list.
Each non-zero item appears in the list only once.

The task is to generate a list T of all such tuples made of non-zero items in L,
which sum is exactly zero. (The sum of a tuple is the sum of all items in it.)
The number of items in the tuples may vary.

------------------------------------------------------------------
Input and Output
------------------------------------------------------------------
Input
The first input line contains single integer 3, it is the number of the task.
The second line contains single integer C, the number of cases.
Next, there are C lines, each represents one case.
Each line contains a list of integers. The list is not empty.
The length of the list is at most 21.

Output
For each input case, the output contains one line with two values NT and NC,
separated be space. LT is the number of the tuples in T and NC is the number
of recursive calls of the function which produced T.

------------------------------------------------------------------
Examples
------------------------------------------------------------------
Input
3
1
0 1 -1 2 -2 3
Output
4 64
# T = [[2, -2], [-1, -2, 3], [1, -1], [1, -1, 2, -2]]
( The contents of T is not part of the output, it is listed here for
( reference only. Also, the order of items in T is not essential. )
# ----------------------------------------------------------------
Input
3
1
0 -2 -3 1 0 -1 4
Output
3 72
# T = [[1, -1], [-3, -1, 4], [-2, -3, 1, 4]]
# ----------------------------------------------------------------
Input
3
1
-1 -2 -3 -4 5 6 7
Output
6 255
# T = [[-3, -4, 7], [-2, -4, 6], [-2, -3, 5],
[-1, -4, 5], [-1, -2, -4, 7], [-1, -2, -3, 6]]
# ----------------------------------------------------------------
Input
3
4
-5 0 0 1 2 3 4 5
-1 1 -2 2
-10 2 4 7 9
-10 -5 2 4 7 9
Output
3 131
3 31
0 63
1 127
# The corresponding lists of tuples are
# T = [[-5, 5], [-5, 2, 3], [-5, 1, 4]]
# T = [[-2, 2], [-1, 1], [-1, 1, -2, 2]]
# T = []
# T = [[-10, -5, 2, 4, 9]]

------------------------------------------------------------------
Solution strategy
------------------------------------------------------------------
The solution is based on the recursive idea:

The input to the solution process is the list L and
also the prescribed sum PS of all elements in each tuple in the resulting list T
which is going to be generated by recursive process.

Although the prescribed sum is equal to zero in the problem specification,
the prescribed sum in subsequent recursive calls is often different from zero.
We will see soon why.

Recursive solution divides list L with n items conceptually into two parts:
The first value V1, and the rest of it, LRest = [V2, V3, ..., Vn].
V1:    LRest:
+--+   +--+--+--+--+--+--+--+
|V1|   |V2|V3|   ....    |Vn|
+--+   +--+--+--+--+--+--+--+
Now, considering the definite solution, we may expect two cases:
1. V1 will not be present in some tuples, and
2. V1 will be present in the remaining tuples.
The recursive idea builds separately two lists, one for case 1 and one for case 2,
ad merges them into a single list T which is the solution.

In case 1, all tuples in LRest which sum is PS are generated by the recursive call.
Those tuples will not contain V1.
In case 2, all tuples in LRest which sum is PS-V1 are generated by the recursive call,
and then item V1 is included in all those tuples. After the inclusion, the sum of each tuple
in case 2 becomes equal to PS.

There are two additional situations which have to be managed  properly:
First, if V1 = 0 then case 2 should not be considered,
and then the definite solution, the list T, is equal to the list created in the first case  only.
Second, when the value of V1 itself is equal to the demanded sum DS,
then also a tuple containing single item V1 should be adedd (as a separate tuple!)
to the list of tuples generated in case 2.

------------------------------------------------------------------
Solution implementation
------------------------------------------------------------------
A proposed simple recursive function F:

Input:
L            : List of values
demandedSum  : The prescribed sum of each tuple returned by the function

Output:
T :  List of all tuples in L which do not contain 0
and which sum is equal to the demandedSum parameter.

Function F description:

If L is empty, F returns empty list.

List T1 is created by calling recursively F with parameters
representing L without the first item, and the demandedSum unchanged.
If the first item in L is 0, then F returns T1 as its result.

Next, list T2 is created by calling recursively F with parameters
representing L without the first item, and the demandedSum decreased by the
value of the first item in L. If T2 is not empty, the first item of L
is added to all tuples in T. Additionally, if the value of the first item of L
is equal to the demandedSum parameter, a tuple containing only this first
item in L is added to T2.
Finally, lists T1 and T2 are merged in to single list T which is returned as the solution.

------------------------------------------------------------------
'''

# ------------------------------------------------------------------------------

pass

'''
------------------------------------------------------------------
------------------------------------------------------------------
We have a pile of oranges to sell. The oranges, it turns out, can be sold
only in packages. Each package can contain from one to few oranges.
The cost of the package depends on its size, that is the the number of oranges in it.
We are given a list of package prices for each possible number of oranges in a package.
the first item in the list is the price for a packet with one orange,
the second item is the price for a packet with two oranges, and so on, the price
for a packet with K oranges is the K-th item in the list.
The price for 0 oranges in package is always 0.

Our task is to divide our pile into a set of orange packages which
sizes are chosen in such way that their total cost is maximum.
All oranges have to be packed. There may be more packages of the same size in our set.

------------------------------------------------------------------
Input and Output
------------------------------------------------------------------
Input
The first input line contains single integer 4, it is the number of the task.
The second line contains single integer C, the number of cases.
Next, there are C lines, each represents one case.
The first value on a line is the number of oranges in the pile, followed by the list of prices.
The list is sorted by the number of oranges in a packet, that is, the first item in the list
is the price for a packet with one orange, the second item is the price for a packet
with two oranges, and so on.
The size of a packet is at most 10, there are no more than 20 oranges.
The list of packet prices is not empty.

Output
For each input case, the output consist of a single line with two values.
The first value is the best price that can be obtained by packaging all oranges,
the second value is the number of recursive calls of the function which produces the result.

------------------------------------------------------------------
Examples
------------------------------------------------------------------

Examples
Input
4
1
7 1 3 4 5 6
Output
10 124
# 7 oranges
# Price: 10 = 4 + 3 + 3
# Packets of 3, 2, and 2 oranges
# ----------------------------------------------------------------
Input
4
1
11 10 21 30 42 52
Output
115 1856
# 11 oranges
# Price: 115 = 52 + 42 + 21
# Packets of 5, 4, and 2 oranges
# ----------------------------------------------------------------
Input
4
1
16 9 21 31 41 53
Output
169 54512
# 16 oranges
# Price: 169 =  53 + 53 + 21 + 21 + 21
# Packets of 5, 5, 2, 2, 2  oranges
# ----------------------------------------------------------------
Input
4
4
4 2 2 2 6
5 10 1 100 4 4 4
10 10 1 100 4 4 4
15 1 4 4 4 10 100
Output
8 16
120 32
310 992
205 30470
# The corresponding packaging:
# Four packets, each of 1 orange
# Packets of 3, 1, and 1 oranges
# Packets of 3, 3, 3, and 1 oranges
# Packets of 6, 6, 2, and 1 oranges

------------------------------------------------------------------
Solution strategy
------------------------------------------------------------------
The solution is based on the recursive idea:

If the number of oranges is 0 (or smaller) the returned cost is also 0.

The solution investigates separately as many options as there are
possible packet sizes, one after another.
It conceptually divides the pile of oranges into two parts.
The first part is a few oranges which can be packed into a single packet.
The second part remains unpacked.
Then, the function asks the recursion to calculate the best price for the
second part, and adds to that value the price of the single packet made of the first part.
This calculation is repeated more times, for each possible size of the first part.
The results of all calculations are compared, the best one is chosen and returned
as a solution. When there are more calculations which yield the same best price,
any of them is chosen as the result.

For example
Prices = [0, 1, 3, 4, 5, 6],  4 oranges

first part: 1 orange, rest: 3 oranges
cost of packing the first part into a single package  = 1
cost of packing the rest, (returned by the recursion) = 4

first part: 2 oranges, rest: 2 oranges
cost of packing the first part into a single package  = 3
cost of packing the rest, (returned by the recursion) = 3

first part: 3 oranges, rest: 1 orange
cost of packing the first part into a single package  = 4
cost of packing the rest, (returned by the recursion) = 1

Of all three calculations, the second one gives the best
total price 3+3 = 6, and this price is returned as the result.

(Zero at the beginning of the list of prices is just a formal value,
due to Python list indexing style, it is not used in calculations.)

------------------------------------------------------------------
Solution implementation
------------------------------------------------------------------
A proposed simple recursive function F:

Input:
L         : List of orange packet prices, the price of packet with
K oranges is at position K in L.
This parameter is not changed in any of the function calls.
Noranges  : The number of oranges to be packed.
Output:
Result : Biggest total price of packages made of all oranges available.

If the number of oranges is 0, F returns 0.

Otherwise, bestPrice variable is set to 0 and updated in the subsequent loop.
The loop starts with packet size 1 and then it loops through all possible packet sizes.
In each loop, the following happens:
A recursive call is performed, with parameter Noranges decreased
by the current packet size.
The current packet price is added to the result of the recursive call.
If the total is bigger than the best price recorded so far (in bestPrice variable),
the bestrPrice variable is updated to the given total.
The number of the loops cannot exceed the maximum available packet size,
and also it cannot exceed the number of oranges available.

Finally, the bestPrice varible value is returned from F as the solution.

------------------------------------------------------------------------------
'''

# ------------------------------------------------------------------------------

'''
------------------------------------------------------------------
------------------------------------------------------------------
Quido is running a bus tour company.
A tour starts in the town and ends at the top of the nearby mountain.
There are some viewpoints on the road to the top.
Quido is deciding at which viewpoints will the bus stop
for tourist sightseeing. He selects the viewpoints according to the rules:
1. The height (above sea level) of each next selected view point
has to be higher than the height of the previous selected viewpoint.
2. The number of selected viewpoints has to be maximum possible
and rule 1. has to be respected.

A list of heights of all viewpoints on the road is given.

For example:
heights  = [5, 4, 2, 7, 5, 9, 1, 2, 8, 3, 9]  # heights are given in hundreds of feet
selected = [5, 7, 8, 9]
# selected viewpoints indexes in the original list are 0, 3, 8, 10, respectively
(See more examples below)

Clearly, there may be more ways to do the selection.
Selection [4, 5, 8, 9] would also satisfy the conditions.
Any solution respecting rules 1. and 2. is satisfactory.

------------------------------------------------------------------
Input and Output
------------------------------------------------------------------
Input
The first input line contains single integer 5, it is the number of the task.
The second line contains single integer C, the number of cases.
Next, there are C lines, each represents one case.
A line contains a list of non-negative integers representing heights of successive
viewpoints on the road. The list is not empty. The length of the list is at most 30.

Output
For each input case, the output consist of a single line with two values,
NS and NC, separated be space.
NS is the maximum number selected viewpoints compliant with Quido's demands.
NC is the number of recursive calls of the function which produces the result.

------------------------------------------------------------------
Examples
------------------------------------------------------------------
Input
5
1
2 4 5 6 7
Output
5 63
# T = [2, 4, 5, 6, 7]
# ----------------------------------------------------------------
Input
5
1
9 8 7 6 5 6 7 8 9 1
Output
5 161
# T = [5, 6, 7, 8, 9]
# ----------------------------------------------------------------
Input
5
3
2 4 2 5 2 6 2 7
5 4 2 7 5 9 1 2 8 3 9
9 1 8 2 7 3 6 4 5 4 13 6 12 7 11 8 10 9 4
Output
5 124
4 259
9 6159
# The corresponding selected viewpoints heights:
# [2, 4, 5, 6, 7]
# [5, 7, 8, 9]
# [1, 2, 3, 4, 5, 6, 7, 8, 10]

------------------------------------------------------------------
Solution strategy
------------------------------------------------------------------
Let us call LSV (List of Selected Viewpoints) the list of selected
viewpoints for the whole tour. LSV has to be found by the recursive solution.

The input to the solution process will be
the list L of viewpoints  V1, V2, ..., Vn,
and also the minimum allowed height (MAH = Minimum Allowed Height)
of the first selected viewpoint. We will see soon why.

Recursive solution divides (conceptually) the list of viewpoints into two parts:
the first viewpoint (V1), and the rest of the tour RT = [V2, V3, ..., Vn]
containing all remaining viewpoints, in their original order.

+--+   +--+--+--+--+--+--+--+
|V1|   |V2|V3|   ....    |Vn|
+--+   +--+--+--+--+--+--+--+

Now, whatever the final solution will be, for V1 there are only two
options: Either it will be NOT included in LSV or it will be included.

Thus, the  solution strategy is to explore both options:
Construct a separate solution for each of the two options,
and choose that solution which produces longer list of viewpoints.

The first option (V1 not included in LSV) is easy to process,
just ask the recursion to find the solution for only RT and pass to it
also the value unchanged value of MAH.

If the height of V1 is smaller than MAH, it is not possible to include V1
in the solution, the second option cannot be considered, and therefore
the list returned from the just mentioned recursive call
is also returned as complete solution LSV.

The second option means that the height of the first selected
viewpoint in RT must bigger than the height of V1,
its height must be at least 1 plus the height of V1.
Thus, the recursive function which finds a solution for RT
takes also as an input parameter the height of V1 increased by 1.
When the recursive call returns the list of selected viewpoints for RT,
then V1 is prepended to that list
and this completes the second option.

Finally, the longer list of the two is returned as a solution LSV.
When their lengths are the same, any of them may be used.

------------------------------------------------------------------
Solution implementation
------------------------------------------------------------------

A proposed simple recursive function F:

Input:
L         : List of viewpoint heights, in the order they appear on the road.
This parameter is not changed in any of the function calls.
Icurr     : Index of the first item in the currently processed part
of L.
MinHeight : The minimum acceptable height of the first viewpoint in the
returned list (Result) of selected viewpoints.
Output:
Result : List of selected viewpoints, satisfying conditions 1. and 2.
(Note that only the length of the result should be printed in output.)

Solution description:

If the part of L to be processed is empty, F returns empty list Result.
That happens when the index Icurr points past the end of L.
Otherwise, the following part of the function is performed.

First, F is called recursively, with Icurr parameter value increased by 1,
and with unchanged value of the minHeight parameter.
Next, the value of L at position Icurr checked.
If it is smaller than the minHeight Value, the list produced
by the recursive call is returned a a result.
If it is not smaller than the minHeight Value, the second recursive call
is performed, again with Icurr parameter value increased by 1,
and also with parmeter minHeight set to the value of the L at position Icurr
increased by 1.  After that, the list returned from the second recursive
call is prepended with the the value in L at position Icurr.

Finaly, F returns as its result the longer one of the two current lists.
If the lengths of the lists are equal, any one of them may be returned as the result.

------------------------------------------------------------------
'''

pass

# * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
#               I N P U T    R E A D I N G
Nlists = int(input())
inputLists = []
for k in range(Nlists):
oneList = list(map(int, input().split()))
inputLists.append(oneList)

# * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
#             P R O C E S S I N G

t1 = time.time()
for aList in inputLists:
# print( 'time', str(t2-t1)[:5] )