Поликарп раздобыл дерево родственных связей. Найденное дерево описывает родственные связи n человек, пронумерованных от 1 до n. Каждый человек в этом дереве имеет не более одного непосредственного предка. Также каждый человек в дереве имеет имя, имена не обязательно уникальные.
Назовем человека с номером a 1-прародителем человека с номером b, если человек с номером a является непосредственным предком человека с номером b.
Назовем человека с номером a k-прародителем (k > 1) человека с номером b, если у человека с номером b есть 1-прародитель, и человек с номером a является (k - 1)-прародителем 1-прародителя человека с номером b.
В найденном дереве родственные связи не образуют циклов. Другими словами не существует человека, который непосредственно или косвенно является собственным прародителем (то есть является x-прародителем самого себя, для некоторого x, x > 0).
Назовем человека с номером a k-сыном человека с номером b, если человек с номером b является k-предком человека с номером a.
Поликарп очень сильно интересуется сколько у кого и каких сыновей. Он записал на листочке m пар чисел vi, ki. Помогите ему для каждой пары vi, ki узнать, сколько существует различных имен, среди всех имен ki-сыновей человека с номером vi.
Выходные данные
Выведите m целых чисел, разделенных пробельными символами, — ответы на записи Поликарпа. Ответы для записей выводите в том порядке, в котором записи встречаются во входных данных.