All Tracks Algorithms Dynamic Programming 2 Dimensional Problem

Palindrome Codiyapa
Tag(s):

Easy-Medium

Problem
Editorial
Analytics

People curse Garg for always having Suffix Array in his problem set.

Having thought upon this for some time, he decided that he will not have this topic again this time.

But as his love for STRINGS never actually ceases to exist, he decided once again to play with strings.

He provides you two strings X and Y.
You need to divide both strings into K parts as per the following rules-

  • The two strings can now be represented as X1X2X3...XK and Y1Y2Y3...YK respectively.
  • Any of the Xi or Yi can be NULL.
  • XiYi has to be necessarily PALINDROME for all i in [1,K ].

K should be as small as possible.

Since Garg has to make output files as soon as possible in order to meet his girlfriend, help him by providing the minimum valid value of K.

Input

The first line of the input contains an integer T - denoting the number of the test cases.
Each test case will be consisting of two lines containing string X and Y respectively .

Output

For each test case, an integer which will denote the value of K is output on a separate line.

Constraints

1<=T<=5
1<=|X|,|Y|<=80, where |X| and |Y| denote lengths of X and Y respectively.
X and Y comprise only lower case characters

Problem Setter:- Shivam Garg

SAMPLE INPUT
2
abc
d
abxy
bayx
SAMPLE OUTPUT
4
2
Explanation

In the first case -

X1 = a , X2 = b , X3 = c , X4 = NULL
Y1 = NULL , Y2 = NULL , Y3 = NULL , Y4 = D

In the second case -

X1 = ab , X2 = xy
Y1 = ba , Y2 = yx

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

Notifications
View All Notifications