Влад и Даша решили переехать в Казань. Метро в Казани выглядит как n станций соединенных n - 1 переездами так, что от каждой станции можно добраться до каждой. Для каждой станции i известна ее глубина под землей depth_i.

Влад выбирает местоположение квартиры, а Даша — местоположение дачи (их выборы могут совпасть). Пусть Влад выбрал станцию i, а Даша станцию j. Назовем непохожестью пары станций количество различных битов в двоичных представлениях depth_i и depth_j. Ребята не поругаются, если четность непохожести станций i и j не будет совпадать с четностью длины кратчайшего пути по переездам от станции i к станции j (длина пути — количество переездов, по которым требуется проехать).

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