شی (یک زیست‌شناس)‌ دارد روی فاصله بین کروموزوم‌ها کار می‌کند؛ یک کروموزوم از دید ساده شی،‌ یک جایگشت از $n$ ژن شماره‌گذاری شده از $1 \ldots n$ است. شی دارد روی فاصله‌های جهش‌یافته بین کروموزوم‌ها تحقیق می‌کند. در تئوری جهش او،‌ هر ریزمجموعه از ژن‌ها که در هر دو کروموزوم کنار یک‌دیگر باشند،‌ یک نقطه تشابه برای این دو کروموزوم است.

یک نقطه تشابه یک جفت دنباله به یک اندازه‌ی $A$ و $A^\prime$ است که $A$ یک زیردنباله متوالی از کروموزوم اول و $A^\prime$ یک زیردنباله متوالی از کروموزوم دوم است که $A$ یک جایشگت از $A^\prime$ است.

می‌خواهیم تعداد نقاط تشابه بین دو کروموزوم به طول بیش‌تر از ۱ را بشماریم.

• در ورودی چندین تست وجود دارد، به ازای هر تست در خط اول تعداد ژن‌ها ($ 2 <= n <= 3000 $) و سپس در هر دو خط بعدی، دو کروموزوم آمده‌است (جایگشتی از ۱ تا $n$).
• ورودی با عدد ۰ تمام می‌شود

به ازای هر تست، در یک خط تعداد نقاط تشابه ۲ کروموزوم داده شده را چاپ کنید.

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

• سوال بعد
• سوال قبل