У Аркадия в саду есть одна необычная яблоня, с которой иногда необходимо собирать яблоки. Так как яблоня необычная, на ней есть n соцветий, они пронумерованы от 1 до n. Соцветие номер 1 находится около корня дерева, любое другое соцветие с номером i (i > 1) расположено на верхнем конце ветки, нижний конец которой расположен в соцветии pi, при этом pi < i.
Когда яблоки созревают, одновременно появляется ровно по одному яблоку в каждом соцветии. В тот же момент все яблоки начинают скатываться вниз по веткам к корню дерева. Каждую секунду все яблоки, кроме находящегося в первом соцветии, одновременно скатываются на одну ветку ближе к корню, то есть, например, из соцветия a яблоко попадет в соцветие pa. Яблоки, находившиеся в первом соцветии, забирает Аркадий. Яблоня необычная, поэтому, если в какой-то момент в одном соцветии оказываются два яблока, они аннигилируют. Так происходит с каждой парой, например, если в соцветие попадет одновременно 5 яблок, то останется только одно яблоко, а если в соцветие попадет одновременно 8 яблок, то не останется ни одного яблока. Таким образом, в каждом соцветии в любой момент времени находится не более одного яблока.
Помогите Аркадию, подсчитайте, сколько яблок он сможет забрать из первого соцветия за один урожай.
Примечание
В первом примере Аркадий соберет всего одно яблоко, которое изначально находилось в соцветии номер 1. Через секунду в это соцветие попадёт еще два яблока из соцветий 2 и 3, но они аннигилируют между собой и Аркадий не сможет собрать ни одно из них.
Во втором примере Аркадий соберет три яблока. Первым он соберет то яблоко, которое изначально находится в соцветии один. Через секунду в соцветие 1 попадет яблоко из соцветия 2 (которое Аркадий тоже соберет), а в соцветия 2 попадут три яблока из соцветий 3, 4 и 5, два из которых аннигилируют между собой, и в соцветии 2 останется всего одно яблоко, которое еще через секунду попадёт в соцветие 1, и Аркадий его соберёт.