Description

"最最喜欢你，绿子。"

"什么程度？"

"像喜欢春天的熊一样。"

"春天的熊？"绿子再次扬起脸，"什么春天的熊？"

"春天的原野里，你一个人正走着，对面走来一只可爱的小熊，浑身的毛活像天鹅绒，眼睛圆鼓鼓的。它对你说道

："你好，小姐，和我一块儿打滚玩好吗？"接着，你就和小熊抱在一起，顺着长满三叶草的山坡"咕噜咕噜"滚下去

，玩了整整一天。你说棒不棒？"

"太棒了。"

"我就这么喜欢你。"

挪威的森林是一片不曾存在的森林。

那个森林很大，里面什么植物都有。

渡边在其中发现了一颗渐渐生长出来的--仙人掌。是的，它会慢慢长出点和环。

渡边很好奇它的最长简单路径长度。

Format

Input

第一行为整数T，表示操作次数。 节点从1开始依次编号。开始仅含1号点。 接下来T行，每行先给出一个整数x和g

，表示连接点和添加的点数。 记p为添加前点数。 若g=1，则表示添加一个点p+1，并与x相连。 若g>1，则表示添

加一个环p+i (1<= i <= g)，点p+1与x相连，点p+i和p+i+1顺次相连(1<= i < g)，点p+g和x相连。 记加入的点数

为N。N <= 100000。

Output

每次操作后，输出答案。

Samples

2 1 1 1 3

1 4