If you have TLE on 9 and you are using Palindomic tree, You should write cin/cout
with "ios_base::sync_with_stdio (false);" instead of scanf/printf

cin/cout with "ios_base::sync_with_stdio (false);" got TLE on 9 for me.

But these lines are faster:

scanf("%s", input);
.....
puts(answer);

where input and answer are char arrays.