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

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

او اکنون در درگاه خرید شاپرک قرار دارد و فرصت زیادی برایش نمانده؛ به او حداقل حروف مورد نیاز برای هر کلاس را بگویید تا کمترین هزینه را پرداخت کند.

ورودی🔗

در خط اول ورودی عدد صحیح $t$ ($1 \le t \le 100$) که برابر تعداد کلاس‌ها است، می‌آید.

در خط اول هر اطلاعات هر کلاس، عدد صحیح $n$ ($1 \le n \le 30$) که برابر تعداد شاگردان استاد در آن کلاس است، می‌آید.

در $n$ خط بعدی، رشته‌های $S_1, S_2, \dots, S_n\,$ (برای هر $1 \le i \le n$، $|S_i| \le 30$) که از حروف الفبای کوچک انگلیسی تشکیل شده‌اند، به ترتیب می‌آیند که نشان‌دهنده کلمات مورد علاقه شاگردان است.

خروجی🔗

برای هر کلاس، کمینه حروفی که استاد باید بخرد را خروجی دهید.

مثال🔗

ورودی نمونه ۱🔗

3
2
aba
bab
2
shaparak
pardis
3
zzz
zz
z

خروجی نمونه ۱🔗

4
10
3

در کلاس اول کافی است دو حرف a و دو حرف b تهیه کند.

در کلاس دوم کافی است سه حرف a و حروف s، h، p، r، k، d‍ و i را یک‌ عدد تهیه کند.

در کلاس سوم تنها کافی است تا ۳ حرف z بخرد تا بتواند هر کلمه مورد علاقه‌ای را بسازد.

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

استاد به تازگی کتاب ریاضیات و مکافات را تألیف کرده‌است. در فصل اول این کتاب تعدادی پرسش به شکل "چند جفت مربع با اضلاع طبیعی، اختلاف مساحت $n$ دارند؟" آمده که باید به آنها پاسخ دهید.

ورودی🔗

در سطر اول ورودی $t$ تعداد پرسش‌های کتاب می‌آید و در سطر $i$ـم از $t$ سطر بعد عدد صحیح $n_i$ می‌آید. $1 \le t \le 1000$ $1 \le n_i \le 10^6$

خروجی🔗

در سطر $i$ـم از $t$ سطر، پاسخ پرسش $i$ـم را خروجی دهید.

مثال🔗

ورودی نمونه ۱🔗

3
5
15
25

خروجی نمونه ۱🔗

1
2
1

تنها دو مربع با اضلاع ۳ و ۲ اختلاف مساحت ۵ دارند.

دو مربع با اضلاع ۱ و ۴ و همچنین دو مربع با اضلاع ۷ و ۸ اختلاف مساحت ۱۵ دارند.

تنها دو مربع با اضلاع ۱۲ و ۱۳ اختلاف مساحت ۲۵ دارند.

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

شاگردان استاد که با شماره‌های $0$ تا $n-1$ شماره‌گذاری شده‌اند، به ترتیب در یک ردیف نشسته‌اند. استاد که از سر و صدای شاگردانش کلافه شده، قصد دارد تا ترتیب نشستن آن‌ها را تغییر دهد.

برای تغییر جای شاگردان، استاد عددی مانند $x$ که $0 \le x \le n-1$ انتخاب می‌کند و سپس برای هر شاگرد مانند $i$ ($0 \le i \le n-1$) او را به جای‌گاه $i \oplus x$ می‌فرستد.

استاد عدد صحیح $x$ را خوب می‌نامد اگر پس از اعمال جابه‌جایی با این عدد، هر شاگرد در یکی از جای‌گاه‌های $0$ تا $n-1$ باقی بماند. به بیان دیگر، عدد $x$ ($0 \le x \le n-1$) خوب است اگر برای هر $i$ که $0 \le i \le n-1$ داشته باشیم $0 \le i \oplus x \le n-1$.

به استاد کمک کنید و تعداد اعداد خوب را برای او بشمارید.

در این‌جا $\oplus$ نشان‌دهنده‌ی یای انحصاری است.

ورودی🔗

در خط اول ورودی عدد صحیح $t$ ($1 \le t \le 10^5$) که برابر تعداد سناریوها است، می‌آید.

در تنها خط هر سناریو، عدد صحیح $n$ ($1 \le n \le 10^{18}$) می‌آید.

خروجی🔗

برای هر سناریو، تنها یک خط شامل پاسخ مسئله در آن سناریو را چاپ کنید.

مثال🔗

ورودی نمونه ۱🔗

3
1
2
3

خروجی نمونه ۱🔗

1
2
1

در هر سه سناریو، $0$ عددی خوب است. در سناریوی دوم که $n = 2$، $1$ نیز عددی خوب است چرا که: $0 \oplus 1 = 1$ $1 \oplus 1 = 0$

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

جنگ جهانی هفدهم نزدیک است و کشورها خود را برای آن آماده می‌کنند. هر کشور تعدادی پادگان دارد و هر پادگان تعدادی سرباز دارد. هر کشور در جنگ تعدادی موج حمله بخصوص با مشخصه‌های مختلف دارد. اگر مشخصه‌ی موجی عدد طبیعی $x$ باشد، آنگاه هر پادگان آن کشور، تا زمانی که تعداد سربازانش از $x$ کمتر نشده، دسته‌های $x$ نفره برای آن موج اعزام می‌کند. تعداد اعضای هر موج را به عنوان افسر ارشد ارتش ارزشمند آن کشور بیابید.

توجه کنید که کشورها کاملاً از هم مستقل هستند و نیز موج‌های یک کشور به ترتیب آماده می‌شوند و افراد یک موج دیگر عضو پادگان نیستند و بنابرین هر سرباز در حداکثر یک موج حضور می‌یابد. برای درک بهتر خواسته سوال به توضیحات نمونه مراجعه کنید.

ورودی🔗

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

در سطر اول کشور $i$ـم دو عدد $n_i$ و $w_i$ به ترتیب از چپ می‌آید که $n_i$ تعداد پادگان‌های آن کشور و $w_i$ تعداد موج‌های آن کشور را نشان می‌دهد.

در سطر بعد $n_i$ عدد با فاصله می‌آید که $j$ـمین آنها $a_{i,j}$ تعداد اعضای پادگان $j$ـم است.

سپس در سطر بعد $w_i$ عدد با فاصله می‌آید که عدد $j$ـم $g_{i,j}$ مشخصه موج $j$ـم را نشان می‌دهد. $1 \le c \le 1000$ $1 \le n_i, w_i, \sum_{i=1}^t n_i, \sum_{i=1}^t w_i, \le 100 \, 000$ $1 \le a_{i,j}, g_{i,j} \le 10^{12}$ $g_{i,1} > g_{i,2} > \dots > g_{i,w_i} \quad (1 \le i \le c)$

خروجی🔗

برای هر کشور در سطری جداگانه تعداد سربازان موج‌ها را به ترتیب خروجی دهید.

مثال🔗

ورودی نمونه ۱🔗

3
3 2
2 7 5
3 2
4 2
4 5 4 5
4 2
1 3
1000000000000
13831120 821120 415

خروجی نمونه ۱🔗

9 4 
16 0 
999989976000 9853440 170150

در این مثال ۳ کشور در جنگ حضور دارند.

کشور اول پادگان‌هایی با ۲، ۷ و ۵ سرباز دارد. در موج اول مشخصه ۳ است و به ترتیب ۰، ۶ و ۳ نفر از پادگان‌ها برای آن اعزام می‌شوند(در مجموع ۹ نفر) و ۲، ۱، ۲ نفر در پادگان‌ها باقی می‌مانند. در موج دوم که مشخصه ۲ است؛ به ترتیب ۲، ۰ و ۲ نفر اعزام می‌شوند(مجموعاً ۴ نفر) و نهایتا تنها یک نفر در پادگان دوم باقی می‌ماند و آن نفر در هیچ موجی شرکت نمی‌کند.

کشور دوم چهار پادگان با ۴ ، ۵، ۴ و ۵ سرباز دارد. در موج اول که مشخصه ۴ هست، همه پادگان‌ها یک دسته ۴ نفره برای آن اعزام می‌کنند و در مجموع ۱۶ نفر اعزام می‌شوند و به ترتیب ۰، ۱، ۰ و ۱ نفر در پادگان‌ها می‌مانند. موج دوم مشخصه ۲ دارد، ولی از آنجا که هیچ پادگانی حداقل دو عضو ندارد، هیچ دسته‌ای اعزام نمی‌شود.

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

استاد که به تازگی از سفر فرنگ بازگشته، هنوز به زبان فارسی عادت نکرده‌است. بنابراین، به مناسبت بازگشت خود، یک سرمونی (ceremony) ترتیب داده‌است.

استاد $n$ نفر را به سرمونی خود دعوت کرده و آن‌ها را با شماره‌های $1$ تا $n$ شماره‌گذاری کرده‌است. هر یک از این $n$ نفر یک کفش چپ و یک کفش راست دارد.

جاکفشی خانه‌ی استاد یک نوار بزرگ شامل $10^9$ خانه است که با شماره‌های $1$ تا $10^9$ شماره‌گذاری شده‌اند. می‌دانیم در ابتدا مهمان $i$-ام کفش چپ خود را در خانه‌ی $L_i$ جاکفشی و کفش راست خود را در خانه‌ی $R_i$ آن قرار داده‌است. تضمین شده که هیچ دو کفشی در یک خانه قرار ندارند.

دوست استاد که می‌خواهد مهمان‌ها موقع خروج از مهمانی دچار مشکل نشوند، دوست دارد که کفش چپ هر مهمان در خانه‌ی سمت چپ (بلافاصله‌ی) کفش سمت راست او باشد. به عبارت دیگر، دوست دارد که اگر در وضعیت نهایی، کفش سمت راست در خانه‌ی $x$ است، کفش سمت چپ در خانه‌ی $x-1$ باشد.

برای رسیدن به این وضعیت، او در هر عملیات می‌تواند دو خانه‌ی مجاور جاکفشی را انتخاب کرده و محتوای آن دو را با هم جابه‌جا کند.

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

ورودی🔗

در خط اول ورودی عدد صحیح $t$ ($1 \le t \le 10^5$) که برابر تعداد سناریوها است، می‌آید.

در خط اول هر سناریو، عدد صحیح $n$ ($1 \le n \le 5 \times 10^5$) که نشان‌دهنده‌ی تعداد مهمان‌های سرمونی‌است، می‌آید.

در هر یک از $n$ خط بعدی سناریو، دو عدد $L_i$ و $R_i$ ($1 \le L_i, R_i \le 10^9\,$) که به ترتیب نشان‌دهنده‌ی جایگاه‌های قرارگیری کفش چپ و راست مهمان $i$ـم‌اند، می‌آیند.

تضمین می‌شود که مجموع $n$ها در همه‌ی سناریوها حداکثر $5 \times 10^5$ است.

خروجی🔗

برای هر سناریو، کمینه‌ی تعداد عملیات‌ها برای رسیدن به وضعیت مطلوب را چاپ کنید.

مثال🔗

ورودی نمونه ۱🔗

3
3
1 6
5 2
3 4
2
1 9
2 10
1
1000000000 1

خروجی نمونه ۱🔗

7
13
999999999

یک دنباله عملیات ممکن که در کمترین مرحله دوست می‌تواند با آن کفش‌ها را مرتب کند: