Фермер Джон заметил, что его коровы чаще спорят, если располагаются слишком близко. Поэтому он хочет открыть серию новых амбаров и распространить коров по ним.

Всякий раз когда ФД строит новый амбар, он соединяет его не более чем одной двунаправленной дорожкой с существующим амбаром. Чтобы обеспечить достаточное удаление коров он иногда хочет определить расстояние от определённого амбара до самого дальнего амбара достижимого от этого амбара. Расстояние между двумя амбарами определяется как количество дорожек, по которым нужно пройти от одного амбара до другого.

ФД имеет q запросов, каждый вида "построить" или "расстояние". Для запроса "построить" ФД строит амбар и соединяет его не более чем с одним из имеющихся амбаров. На запрос "расстояние" ФД спрашивает у Вас от определённого амбара до самого дальнего амбара достижимого от этого амбара по некоторой последовательности дорожек. Гарантируется, что амбар запроса уже построен. Ответьте на запросы ФД.

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

Первая строка содержит целое число q (1 ≤ q ≤ 105). Каждая из последующих q строк содержит запрос. Каждый запрос имеет вид "B p" или "Q k", соответственно построить амбар и соединить его с амбаром p или вывести дальнейшее расстояние по условию задачи от амбара k. Если p = −1, то новый амбар не соединяется ни с каким из старых. Иначе p - номер амбара в порядке построения. Амбары нумеруются от 1, то есть первый построенный амбар будет иметь номер 1, второй - 2, и так далее.

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

Выведите по одной строке для каждого запроса "расстояние". Заметим, что амбар, который не соединён ни с одним из других амбаров имеет самое дальнее расстояние 0.

Пример

Пример ввода соответствует такой сети амбаров:

  (1) 
    \   
     (2)---(4)
    /
  (3)

В запросе 1 мы строим амбар номер 1. В запросе 2 мы спрашиваем расстояние от амбара 1 до самого дальнего из присоединённых к нему амбаров. Поскольку он ещё не соединён с другими амбарами, ответ 0. В запросе 3 мы строим амбар номер 2 и соединяем его с амбаром 1. В запросе 4 мы строим амбар 3 и соединяем его с амбаром 2. В запросе 5 мы спрашиваем расстояние от амбара 3 до самого дальнего присоединённого амбара. Это амбар 1, расстояние до него 2. В запросе 6 мы строим амбар 4 и соединяем его с амбаром 2. В запросе 7 мы спрашиваем расстояние от амбара 2 до самого дальнего присоединённого амбара. Все три амбара 1, 3, 4 находятся на расстоянии 1. Поэтому ответ 1.