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