P19611 [HackerEarth] Sahil loves palindromes.
普及-
题目描述

Sahil loves palindromes.

He has a string with him. But, while he went out for some time, his brother changed his string in his

absence. When he comes back, he is very quick to observe what change has been done to his string.

He observes that the only change that has been done to his string, is that a suffix of the string has

been replaced by its reverse. He is fascinated by this change as now he is able to make a larger

palindrome from this string by removing some (or none) characters from the string. He starts

wondering what change of the given type, which his brother made, should he make on his string so

that he can make the longest possible palindrome by removing zero or more characters. He

wants to know the length of this longest possible palindrome. Since the T20 World Cup is going on

and he loves cricket even more than he loves palindromes, he doesn't want to miss the World Cup.

He turns to you for help. You need to now help him and tell him the answer for the string he has.

Note : You have to make exactly one change of the given type.

Input :

First line contains an integer T, the number of Test cases.

Each test case contains one string s, for which you need to tell the answer to the problem.

Constraints :

T ≤ 100

|s| ≤ 100

Output :

One number per line. The answer to his problem for the string s.

Problem setter : Sahil Prakash

SAMPLE INPUT
2
abcd
abab

SAMPLE OUTPUT
1
4

Explanation

for test 2 : if the suffix 'ab' is reversed. New string = 'abba'. In this case, the longest possible palindrome by removing zero or more characters is of length 4, hence the answer.

输入格式

见题面

输出格式

见题面

样例输入
100 fksujjknoliizkbonmnlobrqbejlykjfwdzfolsexcnwmqmzdblrdejeisriecnahohwabazenvqeksjlfcojnutgnbmponxeuve wvdalbsrlmcyrenctjvbxyooobntxizvgfxriqkvemtwsialsynrwbhlevgbffxlmueumopralputpgnpvgmwozcjfdokcczzgtn vlgxwxsrpafevnqrbpvkuabhddiejbtgocgkzyeoajtvyloabjmxjngosouesokgqqtpqxgqizlgkbgnkvnuktidkfhcttklmdae agvkhirukzhwuusfqdiairebmomyuodwxahgkyauxktsglxwohyyyczktnlpeoldqsjasmxswqkcdjbuszsseuczhponfbqvwcyo oviknsoqdpkvrfnvzsugjkwplmmhokyefgqsbflgwxcncriblekvogmcuyjljjpqqgltnyzjvdzyvjbiolfetrgoqszbbqttweoj covaruyofbztneagwgwoaxreokzkrowvctvvpvmuxlqmrqunyrbzosdefcrwqpruipsxkgtjtjvkzqyyjbxxwcebgvzzkstuhnru vmdowzzvpzvyauxwwdzdyyckrxeanxuikaxgzydqxzqxtpwstxxtyberyirngowsovyntbfqcvpymnqhlpbjqhcoptexjapxvpmo trgvovvdjnkwclhssjjkenjopblksyalrgjidelosvkuhrpbcynhnzvcagougqgyypibvtqpockxwbbybofoncqpjgmrwsrujzxg snwjsggojhokywynyqfjwrbuluouulaobwxveelnnzzlxxzwpgfnxihidxezlenodljjrwzexysvyrrnzydwjkemkknxqaltnwfe selpedkcwdsvevrnhxzrhmoxobtcxyipethiwtlsxfnbagohdpbmdrkttfvsdgkhzrrwmeqjjemlkcvqrwcwpoqktndwtpfvizru dhgpnsayvvqotsnjhfvauazqpglxfesllaabsabpyrgrjtcsayvuywkqcxnibhvphvqcxrtvizpturowrjrsfdijdxrefotojjsh cockntgklwgcfzwmfevicpojdizptuwwiaivuqhhmqltrihymdiquxzzhbocvkadnlahbkqqabltjtsyyaosxqrgtijosjthwtqy fgqfibztutrstimtagztokjiwcqsxgsdnikxmlqiekdysptuvsnldwubaktxsmchwpeiaxrhhuhzlatjuiuzgoagaufvgkcczjnb geinapolpjukrpjxfmfigkdouhsvqfxwlfjlxxzogtazkmysydaeofukmmgfufbfkntjmsytlyuyktqiwsomziznxhsrmuwyhpiv hgovglvrelbcfsreaqrxxkolgnjpcrkmzbjgoezsrcwyuncxfvuehlpnabecspqusbcgfbaydywaoyxtwtaderresxjnobhgdjok mojrnhrbioweiyhoqavkyexohgvmrlxdcixpposxdqdnplbhnwrlcpcmxxypkxumfrdxivwnoaafldmycdmguossntjxqfkyxnxh ltubtuggzshbxvkslemaxxzqclqbbnioicpeyxmyrtboqlidqwdptfhwqxzrmifxkwbltplkjmbbajfsgkjbprzgqzzfhhctdfgz urlfgmjiwocealhqehwvixareemkjtlfmwlsjwahkenkqucudarlyrcevpogkzmwwzphxrohwdtozwkdwcqwtvbrmrzwrnspojyl dosbrorqmbvkdohzjkqvbpruflltxjfazzdqpujbvgmzuvydfqaihtdmfogealezmjscdddyjrzgozlvpmexfhlmxrqxewxtfrvk uajduklikxezjiyqrkdodvokundbeymyaxduhpftmjvxtvnkfsalqovkbalhyzfawlvgaazolwlesyqztskjhhtkhgshgziekfkk fmysilyamoafgmopuhcbpulvvtcgamshatzjexlqnlvvyjnuspvilifgbhodwhkwajhgitxveuteggyyxwiieqqizflvoyuohbws utnbqghwoiwlghtkxmuytiwhgqxptthqpxtffabuixfogbbdpxeihappsmhlfqdunwbvxcrhcyyizboqauyiunzobgbhxfdmbfja jaklzkwalmrlgpvcfxqgdrpcyvrcaaclbozayvaljtzpjwtqtjwxcobbjsdlvhwwwvywsakbujsfflvzwtyzhbasufdpmankxljq ltthemmjzhkwbkxkmzdiegzqiodgzmymhrulfiwhqjfttcfhbirfrsxzgchhohwvzsigafnsounjwttzdkgufewlidvxlrumjdul kkeyerhbkcaophkunghvmcuzvrnewhqgrwgynpzasbqhkcbzjixxntyiklnisfomdwksmlseoknbnocyyzxlvvufgjqaqeotbylp lgtcsiffwhfwjciexeldpbghiuclvnaivvkodpvbzbxifhmdlxicbqjjlluibuqyrbouskvrnsbuanznnisoabzlpttspmqgnfah rxzgpaarqahfkzvkauyrptjefcmujmcaldgafiuxibcsazfcvdukwfqejcysqcudfcgnlaktdpodothmydwulpautzpmdjpjmvwz xiuaxifmdnybswydnyyhznvdykokimlfugisqnguagxtevyswwbvlwakiqwsckazqirgvzcyhatlxrftqgpderppiojkyjjotcwr dbpkdkyadduvmlzscqjkevxceisanrrqsgdvsbvxgrtucunhkyrptqtabmaodrexzjstmpqtjjnldcsqbmfweywfmytpramqjgjy wcrhlgsrjnhmbokfohnbhgqzifpulbsjflqqrljcysobizixivypeqqmvigjlauqllidysfymwzvxhshdqyhipvgxepiglyswgxw aeunatizdagisfrcumitszbzlbrjhqgkucxvwfubhdjbiadcmovhnygazxminusjwreuybvhgeioeostcparngsofgyuatdwkkrl nosttdhzrbsvqumfagthmrbmkhlxteigscbnfknwlhrbcggembobsrpfyaergmzbqaowmduxnoypugvihjjcbzhbbnvizujpxznj fihswhjsqgazqkbtlkumxpuymfqjhdumndglnpddxgcnsegdqdpoukogreryimmxpsjejohhukwmqfpiifwcrllkrcjbqvziqimz yuitgfhymxgwefaxqlhjqqlgokogudhsxqnfxvdjulhyqhvitesjxdrnpgtjjadisrproucifjgyrdgkhyvgdmtsumddnhnhaezo ybwgleechkoqljxqvsjqfovuvlbxrclqehwrlcvumjnzumqrebjlrhfpujmllybrhzktbfpqqepkqhexknicworqxdckbfelhoei uvakaqxszdpksyopmfhlijxmrbxyqdimajyabxtaakmtiakwfrjqdheukbuagcoglnjmkepnobizesvjlfbqofmyigbojpxweilr maecdmbhgxtrewiucuumdxdonaktivkwxoybaakizfafckzegtsjrvxgxibhfmdfccifesndyniczjigcapvwpdvzfdetglvktao ootodbqdkyjpyamwpqsoxxvqdglqcmeqcaefbukoutfuwtrnllciizanhmdjakzckfjnzudtpkolehbpudacearlovxqhwstcegd ymzpwpbcwcsqhuunulalixbpwwkyardafcpbrsepuyhdsdsoptzzqbrmxbmzsqzzuobohhddhnjzqbphurhnuyzrzosugrtafwoo dusmjblzedhzuoooophndzjjsfmzbcohwithlhhpmqqgegwuwfhzetlyyxxbzniyxefinoazesfkzdeviowohhmhgligbtgyxnjk cllgfstevxbdlyruhfboskwtfcucrfotszcxtvcoudrgdkalrezlqxfvbbzsinoaosxhnbxhfqpkcsvtwwemtlhuognwvdylvwui xrrejjplbmgxjmleaszoaonxrnkmjewjxppgygtbtzaellklfjchzreseogquebruqzuzsyuryyfmiqruuzvlfoquuiqzjivbjra cpuvouaafttbnuwzakrwhzmiiudjgwmimgfcbicibxjqsfpssiozhahrxmbdinnwvuyyccgfapwsxnmpwcodexvdlyivnvsksqjw tpcvhypelbvjflnjiknvkvqxtihnbsjwklrrlgxzjsiqfxzpjoktmaqhlauosdkerbvejufuoqktnlixcusqvlxilrwfwikplhuu ebqsrcohpwgtryjojgywzwcyeonpxjlbldwefklwitqbuzrdipcjnehtuxkrixtvapahbnejjwldxeifukrjqadkzneilzfnqhvr xbcgxplwuteqevzuxehxulhhmmucurvrsxzrnkohduzhpyemdllzysgkfambshsmgtgtdwcgqdqhcuvhhhgfbmpgodjimbvsudoz zsgrwyyauvjberggfxotcycobziycyxdrfupdupxpaawricwfqpjotzssiqwgnzzvvqyphyhhydyhhwoxoaohzgcjyyslyrgtihl phszhxzoewfdkhttgzvqxuilsbtnjcybjscrpbhvxozjvsdcuyutscgmdaapeysorufivoevdfgyzjavkwreyxreztvetpsmjzvg nbdqikrjvtffqwkqvduxwrbrgverwbajefcmpvvlocsgaexwhttflwxtrdnpgnakscykzvxoypwawtwdprlapivinixtvydqcdcc yzswqoxmkvszpdbenwnafktckyunbwpzvjyozxajusijvjqiidknpfrafmpgigigpiuohwabpilmubxcghpxnizswobfwlnlvjcc fcdwmqjgtgibpzzeiaxepalllazgjdkrfnnrgyyzgibwicasczytzmfmmguwjenquchabhzhscfaeguhhsahehvtpspyweosiysj hurzyybdexmmsovwwsplkgmhmcbvawgkszlqynvcmhqewnduguhqbtzpybmyxtkpswhqldvxklcizfcfzmvchxufyggxzqoumvkz yfxltbtsiyzhkwmrtgxtodqqtekicuhacglvhfprfozpmniivfbjkuzgalqcgzfkgqfpxuhckityxcgsjkduefceqsjyroizenre jaivicufgazpkclqhpvajeybuhcawtegtpbdrvkzyjqkoebxtwxdcygyfkybgdjzunfnkpmibctrgwocsofwmnutxswdxgfrvmef dsqgvlxdhohzcoxqbtjbnfgnnlgiznqdfgjcrhiyxpzbeyrfrcgehptxaahcnzfsfqxyzfywuxxyxogoqovadozgqgidinyndvod ambukzthpzygnvirlhzcphfxudnzabeangxzfqjurjcgemzptytlfzkbexbfahhqnepswappjtwpgxhzyamfzxhgwknzrupfbgzx hqnskliqipripeordxzbhmaaiphjwjjfzwxjjfztutcmzqdcncfwqiwaxgkvptcoraaahbteuvqtnvxczdyplxpkfbiuwkknmkpu mlygiqawnxamcbdnauafyizuulkhwzdkmdqvtsrgstuwuzkutkzruamomyvkzyumbmhwhaebtaxqzhkttmmnmaeayzmyagmdtvcc xidsjaiikvddhqtvqxwryirardemygoxorpztyidtljadcxubtlzecavhgjhoxeeqtejtonobyqfaobdjocnsekzmtgasmhkflwb bjpchghjukmdyqtqxdplzxotjveriaujljlupvflftpeliwinmwolkixfoonqiydtjzlgewmzlskvovlcrbqbjnizdxrnvuggvrn zqzadtlzjgmozneazrkawhsjcoriklvlbwmerzfbfrrghvggosgmzavbrolbzjochchzbociitopqwxgofsngpqzfeafnqjutsvw hzfpuveksdsgimwqbmphsrofizcdsxzzzgotcugwxychlayonnxffnnnnpsfotenaujeqpappewafurukobpcoerfwwwpcjryuvq jxfzcdbhasbkjczntdeybauqegicafumdzlfeooghrqsvrfowjnxljqrratufngkotruhfbqytiunnijyxjljzcabxuimatctkxd satqtckgrvsqsbdbcgeddynsbguwttzlvtdpvqxmlrefuijwonbtnploxilqdkdzdhqazpnmhrtbzeaprdlhsyvsgiimvolyvdbw sokzhddjifabilidkgvsofejtrkqulmnbwokcttkywnhhwmrchmsoqcikmyezntalimndgzccnlljxfngrfwjhetvfywsrydbltf rsjvhugqtlfbelxouehsjhobzngcybhrwqodmwwhkbiooicjmmbvtrysegveievexlhjidrshbgvjlexxhsqzqlfzimhmjllvsvd yoxfrfadqhapqvgrntzmbltpuebpzyuzorehxgkpplfgglzvgyihjbyeibvhbqipjmxgujymwdueqtawsidbjdhtfdagvkyeyxnt glfdqbjgujcmrhqdkxwrczyzjygivtddgkiylsefdguvpkabjwtoxtnjrvroowtwgcurwayziswxewzqvugsntbgpuwfqpeytarr bqtjkpjroihlcnfrijzzdxhwonwknobqgwcqmljctsnxhuqqdrrjoafcpbmdrqvxmxqaizcdsrczmurrllaznhedlqicgdctdsvl tarlrtnfogzztzbhhfksxuwexyzaswomwfzqymxovwqowrvfyhzvbvbbwcdozraxwanxolljhdadwxkufjsifvldaprbguyfwmcm zpygtympxwmeignpbysbplcwhdbfpfsqwswpqkhpjturzjicjagznivvlyacfusbmrtedauovohwxpygpefdpcaccahhxzljseoy eimbyuxvjxdbejgtngxqiezfgkpaqfyunlvlhuiqsltwwzrkfqcqxdxdqofgtebiryvyvdqnrklnjezrudhrhgwzvcfogizzjuxe anrrzegjiicellwurstmwzdchcbswawyqnrptyabicgtpeqhyjvvkyzucdmbdjzvyrlsrntzqbuhfkoewkbgkacndrqhapcaipsz doavrvcxhtddfempeoekfuthmxiwncwsqynitrhbkmgrqshwjngqkbyyziuoksgbrvlmospbgyswqbubpdsbesbfavtkqznjwyxl snmynewdithzwzacrbitybdqdrzzrxmmmamzhjepcnoamqcftkaroeirxjsoihcujpvqachcpveenglgtmajqkcptwfcdiynxufx ynbnkhrypdekrgthqxykudozlmokiujgjmuttntlsavjgpsxmqhiwxijjwwsqfabuwxpkqaeswqznkybdhkzesinqehjmikiehxq aavsyntlxrmayyzesksjqbscjcmqmkgmmbgkqavorjoskqycaqlsufvdijtwvcihdorwookiayckqaostclnhgsrronnqvuvmorc ebkecoqurfnmjybqgtixjxkbvhxhxqjbswiwkyqdfdpodshjorhxotzjaysxocbiyjekjxqpchfgamrofyluumfukyuzcxhcgoop negromzoarcgrpclcjiojenlbxpjneyakfryttmtkqbbgdpknxywbokclznyflasstqlmfhwxiafoppbmqzpeltrngrutrmmkfzx mivjrvpfmgiyyjpevixkqoekhryswxrigmtzkkgwroxrxowuxtepkjzrczlyxcifrdgdomzhayyznuwmqcbaldrpcdpbhxgybmdp adyabwcqtacjcelqhefljvnruvrxivokamlbjpsepwntaajjerxookhifygpvuavhnzsetwvplosnabrryhhkopsnvhisjebyfvc yrxneofrojkhjsougfmvdvgvfmyfrtipmhcsvklltvucpiwyqkvtgbqnposgjcxxkcpfmatfxnhpygnosihamxnbnikwmjvwlkez mzelmoakwpyoyhpmeeptobrdlmzywfykeeytuydqoeholwascrlttdwgpxeofcajjyedzkunobdzzftdwfwrksxbqcpvgsgpqnvr xpglsjmtqgwpnvgxneyfiqaqkjicwdutuagomshcafrnaamqenvofyepjorfrlanogbaakcbqwoswdicqgqvewknnduepwsfctfe gjfwfwqbzbdrhvmluyahbwnsshxwdcajoihtexxfycwfyksuiudlqqekydgbijmwrtpxqmcrrywrkrlsnqdggjqgnzjvivtbokyh zayqawhkpsedkjjqvbzkckhkianyklfjnfznegztafykrjdmlewpofcwfpvpbcbqiagmjhhlniwgrbsefquvxwuclptotufbxlpg szrhhpnyqhfxzztwvnyieuzxoeblrstltltaaibtqiqphloeyooeincxrfkkxewtrptrxwmpedhnqvrrlgvuvztnefzejvxamsum rgbvlilefcvrkqngsivynwexsdzewvqpeumrexvmcqdojswbatznqemihooflhupdhhhgctivyzeqvhspgifmwpukfbwownrfuzl zuwwtvalqhghpoockfyxlztbvitcfuqeomcjjevbnbjcrxgbfeysettbcmehgunxirgrvbsiedkvdtzixzabvtfziliofxlpouij varcgdzjwarwarxxmewupejwbwlpqtaowtscwrlvucrwvqthvpckvnhylupeopumimogfbbzfsvalqjghnqcazcourskimwqamxf nahsveugvdmctehtgjjaddklricrubzhbgbykvefasktxrpfayfdcrrvztntwmazudyeyemyxwswpjbrhixlzohyhwtfiveeyciw jwwguqejzfbjnywomdovbhajeepejycuwyarreaqldbabyopdekfnmqrtgvcexwcxytoewfpzgrbgfskldpyrfpklmorlkuikpxo leflmwotdgdolumdzdnnpcecoalzqkpboxmcvavzjanuucxwfnjxppzdqmeiwwjmtypoampjpfglhfhosqnhipnybtiaprmkrbbu qqdfxlqgryvjqktyzgydzidrcrdtvgnlztswgidxiajbkcbmicrjkwcmniiiovvnqnkxwpwgpfjbhlprngdzcfmsnuccryrklbhj qdqhjbjsmykbhnblupdilimcgfmrhvdzbtjmusejsomzbnnwesgpauugziaigdkhyttslxdfmqhpfunkmvbnpxvrgvzmyjvwcorp nwxbmeruaggmchbthzmpumdvxytcmmtzjqbxwurwcxlghoconodkcghaeaesnxtyqwvosnlvkybrmdfcskowqvwwxcqkckisgggb ttwdrxxgdekxpythvsgsuwfwipqrvzsquowontuqzgpqgjybbgvxccwnumerlwiimgwzzqsayhreqrhtxerbjnodbuwpqgxemten lwojdhnwywpxaiajxrozlloerlieemtpkhaqopmoldlnomzlfnkqayuslfyrtriebiwrxkgknrydfxpkmzdnazhlehdaalebuctt mbebscfabumntpctrjhxqkxtvdurfplrqrvltanwwzjrronixufqgdjbgfvovihnzcauenqanbsgpfqpbxfhcokjtfzqnggojgin uaojeirtphkqepxhdhszptrezxtiedyagmlkwcfllqbrfayljsmaldfndavjftjlhwvfabqlrtcytdjfxvflbmyemvnupwfyudgu
样例输出
17 7 1 21 3 31 19 29 13 39 1 11 1 3 13 11 7 23 21 16 17 13 17 19 3 9 21 1 27 21 24 19 30 5 17 11 23 5 25 29 25 31 35 11 17 1 10 21 5 35 35 29 21 12 17 3 23