1.

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, WS09
* Problem: 497 Strategic Defense Initiative
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=6&page=show_problem&problem=438
*
* @author Christoph Hausmann
* @version 0.1, 11/18/2009
*
* Method : LIS
* Status : Accepted
* Runtime: 0.180
*/

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.nio.IntBuffer;
import java.util.ArrayList;
import java.util.List;


public class StrategicDefenseInitiative_497 {
public static void main(String... args) throws NumberFormatException, IOException {
final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

final int numberOfTests = Integer.parseInt(br.readLine());

br.readLine();

for(int curTest = 0; curTest < numberOfTests; curTest++) {

final List<Integer> a = new ArrayList<Integer>();

while(true) {
final String curLine = br.readLine();

if(curLine == null || curLine.length() == 0) {
break;
}

a.add(Integer.parseInt(curLine));
}

if(a.size() <= 0)
continue;

final IntBuffer v = IntBuffer.allocate(a.size());
final IntBuffer vPred = IntBuffer.allocate(a.size());

v.put(1);
vPred.put(-1);
int imax = 0;

for (int i = 1; i < a.size(); i++) {
v.put(1);
vPred.put(-1);
for (int j = 0; j < i; j++)
if (a.get(j) < a.get(i) && v.get(j) + 1 > v.get(i)) {
v.put(v.position() - 1, v.get(j) + 1);
vPred.put(vPred.position() - 1, j);
}
if (v.get(i) > v.get(imax))
imax = i;
}


System.out.println("Max hits: " + v.get(imax));
recoverSubstring(a, vPred, imax);

if(curTest < numberOfTests-1)
System.out.println();

}
}

private static void recoverSubstring(List<Integer> a, IntBuffer vPred, int i) {
if (vPred.get(i) != -1)
recoverSubstring(a, vPred, vPred.get(i));
System.out.println(a.get(i));
}

}