Time’s up little one… let’s see the code he growled. The suspense was excruciating. I could hear little pearls of sweat drip from my forehead onto the ground. SILENCE. Drip, drip. I felt myself slip into unconsciousness… a bright sunny day… probably a national holiday… the wind caresses the tall grass and the old willow in my parent’s backyard. I was careless back then, free to soar the sky and chase time! My brother had just returned back from his latest mission…he was a soldier. Laughter and smoke from the barbeque filled the air. That smell… wait… my eyes started opening. I was surrounded by flames. Igor must have activated the auto-destruct button from the control panel. I started suffocating on the dense smoke… this was the end. My lungs could not withstand the lack of oxygen and my body started shrivelling up like a raisin. I tried to slither my way towards the emergency escape pit when a flash of light caught the corner of my eye. It was the center screen. Igor must have forgotten about it… pretty sloppy for a grade A terrorist! I gathered all of my strength and dragged my body in that direction. It was a basic map of the world with several red nodes on it. Next to the map there was a huge key… I quickly scanned it for additional information. The nodes were shaped like a giant tree… NB… nuclear bombs! So this was Igor’s demented plan all along? Wiping out civilisation? Each node is labelled from 1 to N. Beneath each number there is one lowercase letter. Connections started appearing in between the nodes… Igor was probably planning detonations. Each detonation route starts with the first node and forms a palindrome out of the lower case letters… the detonation code. Knowing Igor… he’s probably going to choose the longest route for his massive annihilation scheme! What is it about pain that brings joy to people? I suddenly felt very dizzy… the smoke… the flames… they were engulfing everything. If I could figure out the longest route before Igor, I could most probably hack into his detonation panel and stop the entire operation. But time is not on my side… especially since I’ve got about 4 minutes of consciousness left… smoke… grassy plains… free spirits!

You are given a tree with nodes labled from 1 to N. Each nodes contains a lower case letter from the english alphabet. Find the longest palindrome you can form out of all of the nodes starting from the node labled 1.


The first line of the input contains a number T, the number of tests.
For each test, the input contains a line with n, the number of nodes, then a line with n letters, representing the letters associated to the nodes, and finally n-1 lines, each describing a connection between two nodes.


For each test, print a line containing the maximum length of the palindrome.


1 ≤ T ≤ 5
1 ≤ N ≤ 100 000
The letters are lowercase letters of the latin alphabet.


1 2
2 3
3 4
1 5
1 2
2 3
3 4
1 5

Sponsors Gold