CRSCNTRY - Cross-country


Agness, a student of computer science, is very keen on cross­country running, and she participates in races organised every Saturday in a big park. Each of the participants obtains a route card, which specifies a sequence of checkpoints, which they need to visit in the given order. Agness is a very atractive girl, and a number of male runners have asked her for a date. She would like to choose one of them during the race. Thus she invited all her admirers to the park on Saturday and let the race decide. The winner would be the one, who scores the maximum number of points. Agnes came up with the following rules:

  • a runner scores one point if he meets Agnes at the checkpoint,
  • if a runner scored a point at the checkpoint, then he cannot get another point unless he and Agnes move to the next checkpoints specified in their cards.
  • route specified by the card may cross the same checkpoint more than once,
  • each competitor must strictly follow race instructions written on his card.

Between two consecutive meetings, the girl and the competitors may visit any number of checkpoints. The boys will be really doing their best, so you may assume, that each of them will be able to visit any number of checkpoints whilst Agnes runs between two consecutive ones on her route.

Task

Write a program which for each data set from a sequence of several data sets:

  • reads in the contents of Agnes' race card and contents of race cards presented to Tom,
  • computes the greatest number of times Tom is able to meet Agnes during the race,
  • writes it to output.

Input

There is one integer d in the first line of the input file, 1 <= d <= 10. This is the number of data sets. The data sets follow. Each data set consists of a number of lines, with the first one specifying the route in Agnes' race card. Consecutive lines contain routes on cards presented to Tom. At least one route is presented to Tom. The route is given as a sequence of integers from interval [1, 1000] separated by single spaces. Number 0 stands for the end of the route, though when it is placed at the beginning of the line it means the end of data set. There are at least two and at most 2000 checkpoints in a race card.

Output

The i-th line of the output file should contain one integer. That integer should equal the greatest number of times Tom is able to meet with Agnes for race cards given in the i-th data set.

Example

Sample input:
3
1 2 3 4 5 6 7 8 9 0
1 3 8 2 0
2 5 7 8 9 0
1 1 1 1 1 1 2 3 0
1 3 1 3 5 7 8 9 3 4 0
1 2 35 0
0
1 3 5 7 0
3 7 5 1 0
0
1 2 1 1 0
1 1 1 0
0

Sample output:
6
2
3

hide comments
sharif ullah: 2016-08-28 19:35:30

what the need of the history of problem statement !!! what is the relation about score and point!!!
To solve this Just FOLLOW Input !!!

aish_dutt: 2016-08-23 16:32:41

After a long struggle with input finally got AC :)

singh1495: 2016-08-19 20:18:18

easy one first go ):

sarthak7838: 2016-06-15 21:03:28

Ac in one go !!Simple DP

conquistador: 2016-06-09 12:11:24

could somebody suggest similar lcs and dp problems for beginners?

ADITYA PRAKASH: 2016-06-01 10:59:03

Sorry silly question. Got it!

Last edit: 2016-06-01 14:13:34
fly_sky12: 2016-05-20 11:53:04

learnt a new algo

avisheksanvas: 2016-05-18 06:30:04

Why is it that the 2D array which stores the length of the Longest Subsequence had to be declared as global? It gives runtime error if declared inside the lcs() function.

ajay_5097: 2016-04-14 22:29:50

this question is hard to understand but easy to implement!
please take care of input type !!otherwise it wouldbe wrong answer....
like mine!!

Last edit: 2016-04-14 22:30:18
Deepak : 2016-03-30 23:01:25

lcs..


Added by:adrian
Date:2004-06-08
Time limit:5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:III Polish Collegiate Team Programming Contest (AMPPZ), 1998