یک درخت $n$ راسی به شما داده شده است. روی هر یک از یال‌های درخت عددی بین $1$ و $n-1$ نوشته شده و همه این اعداد متمایز هستند. به مسیر بین دو راس $i$ و $j$ مناسب می‌گوییم اگر

• $i$ و $j$ متفاوت باشند
• هیچ کدام از اعداد نوشته شده بر روی یال‌های مسیر بر دیگری بخشپذیر نباشد

شما باید برنامه‌ای بنویسید که با دریافت اطلاعات درخت تعداد میسرهای مناسب آن را پیدا کند.

• در سطر اول ورودی، عدد $n$، تعداد رئوس درخت قرار دارد.
• در $n-1$ سطر بعدی در هر سطر به ترتیب سه عدد $u$ ، $v$ و $c$ آمده است که نشان می‌دهد یک یال بین دو راس $u$ و $v$ درخت قرار دارد که عدد نوشته شده روی آن $c$ است.
• همه‌ی اعداد نوشته شده روی یال‌های درخت متفاوت و بین $1$ و $n-1$ هستند. هم‌چنین ورودی یک درخت را توصیف می‌کند.
• $1 \le n \le 100000$
• در حداقل $40$ درصد تست‌ها $n$ از $3000$ بیش‌تر نیست.

در تنها سطر خروجی پاسخ سوال را چاپ نمایید.

• محدودیت زمان: ۴ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

در مثال نمونه مسیرهای بین رئوس $(1,2)$ ، $(1,3)$ ، $(2,3)$ و $(2,4)$ مناسب هستند.