You are given a string s. And you are given three characters x which may or may not change to some given characters y respectively. Now if some x decides to change then all occurrences of x will change to y in the string. Lets call the new formed String after reversing s and applying the possible change operations as p. Determine the longest common substring of s and all possible p.
String contains small alphabets only.
All the x for a given test case will be unique.
Input
First line contains t test cases, t<=10
Each test case contains 4 lines as follows
First Line contains String s, |s|<=10^4
Next three line contains two space separated characters x which will change to y respectively
Output
Output length of longest common substring of s and all possible p on new line for each test case.
Setter : Akshay Miterani
s=[abc]
p=[cba,caa,cbb,cab,cba,caa,cbb,cab]
Hence longest common substring is for abc and cab which is ab of length 2
Hence answer is 2
