В наши дни в интернете можно делать все, что угодно. Например, Вы можете использовать различные веб-сайты, чтобы завести виртуальных друзей. Для некоторых людей развитие социальной сети (друзей, друзей друзей, друзей друзей и так далее) стало увлекательным хобби. Так же, как одни собирают марки, другие собирают виртуальных друзей.

Ваша задача - наблюдать за взаимодействиями на таком веб-сайте и отслеживать размер сети каждого человека.

Считайте, что всякая дружба взаимна. Если Фред - друг Барни, то Барни также друг Фреда.

Входные данные

Первая строка содержит количество тестов. Каждый тест начинается со строки, содержащей целое число f - количество сформированных дружеских отношений, не превышающее 105. Каждая из следующих f строк содержит имена двух людей, которые только что подружились. Имя представляет собой строку от 1 до 20 букв (в верхнем или нижнем регистре).

Выходные данные

Каждый раз, когда завязывается дружба, выведите в строку одно целое число - количество людей в социальной сети двух людей, которые только что стали друзьями.