You have to output the number of cities that can be disconnected by destroying 1 city + 1(for the destroyed city), not the city to be destroyed.

Hence in test3, we destroy city 2, and hence 1 friend is unhappy.

if we take p=2, won't n!!mod p^a always give 1??(irrespective of even a)