#2617 Longest Chulseung Subsequence

11  5 s   128 MB  

Description

춸씅의 숙적 쭈ㅖ리쒄뿌ㅖ는 고민이 생겼다. 세상 곳곳에는 춸씅이 너무 너무 많아서...("because, chulseung is the universal set") 질색인 쭈ㅖ리쒄뿌ㅖ는 적(춸씅)을 이기기 위해서는 역시 춸씅을 확실히 알아야 한다는 생각에, longest chulseung subsequence를 알고 싶어한다. 문자열 aegggga와 aa의 longest chulseung subsequence는 aa이다. 하지만 쭈ㅖ리쒄뿌ㅖ는 겨우 2개의 문자열에 만족하지 않는다. 그래서 이런 쭈ㅖ리쒄뿌ㅖ를 위해 3개의 문자열의 longest chulseung subsequence의 길이를 구해주자.

Input

test case $t$ $(1 \leq t \leq 100)$가 들어오고 문자열 a, b, c 가 순서대로 들어온다. (단, 각 문자열의 길이는 100을 넘지 않는다)

Output

문자열 a, b, c의 longest chulseung subsequence의 길이를 출력한다.

Sample Input

Sample Output

1
abcdefghijklmn bdefg efg
3

Source

2015 ANSI Summer Coding Camp / BOJ 1958 / data set by wowoto9772(최승주)