مخابرات ACM خدمات ارتباطی تماس‌های بین‌المللی را برعهده دارد. هزینه‌های تماس با کشورهای دیگر متفاوت هستند. شرکت این هزینه‌ها را در جدولی نگه‌داری می‌کند که در هر سطرش کد یک کشور و هزینه تماس با آن کشور قرار دارد. هنگام تماس یک سیستم اتوماتیک کدکشور را با توجه به ارقام سمت چپ شماره‌های هشت‌رقمی پیدا می‌کند و باتوجه به نرخ کشور در جدول هزینه تماس را تعیین می‌کند. سیستم اتوماتیک لیست کدکشورها را بصورت نزولی مرتب می‌کند و هنگام تماس، سیستم از بالای این لیست به سمت پایین حرکت می‌کند و اولین کدکشوری را پیدا می‌کند که یک پیشوند از شماره گرفته‌شده است. حال با توجه‌به هزینه آن کشور هزینه تماس را تعیین می‌کند. به‌ازای هر شماره هشت‌رقمی، حتما کدکشوری وجود دارد که پیشوند آن شماره هشت‌رقمی باشد. باتوجه به تعداد زیاد سطرهای این جدول قصد داریم تعداد سطرهای این جدول را کمینه کنیم بطوری‌که هزینه تماس هیچ شماره هشت‌رقمی‌ای تغییر نمی‌کند. وظیفه شما این است که این مقدار کمینه را به ازای هر تست‌کیس به‌دست آورید.

در خط اول ورودی $t$ ($ 1 \leq t \leq 20$) به معنی تعداد تست‌کیس‌های ورودی است. هر تست‌کیس با عدد $N$ ($ 1 \leq N \leq 1000 $) شروع می‌شود که تعداد سطرهای جدول اولیه است. در $N$ سطر بعد، در هر سطر دو عدد به شکل $code cost$ آمده‌است که $code$ عددی بین $1$ تا $9999$ است و $cost$ ($ 1 \leq cost \leq 100$) به‌معنی هزینه تماس کد داده شده است. سطرهای یک تست‌کیس دارای $code$ های یکسان نیستند.

به ازای هر تست‌کیس در یک خط جداگانه، عدد خواسته‌شده در صورت سوال را چاپ کنید.

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

• سوال قبل