Пропонуємо математичну головоломку. Нехай ми маємо натуральне число ~n~. Запишемо його у перший рядок аркушу. Віднімемо від нього його першу цифру і результат запишемо у другий рядок. Якщо результат не 0, то від отриманого числа віднімемо його першу цифру і запишемо у новий рядок. Продовжуємо це робити до тих пір, поки не запишемо у рядок 0. Так ми отримали ~k~ рядків, і в ~k~-му рядку записано 0.

Наприклад, для ~n~ = 10 ми отримаємо:

• 10
• 9
• 0

Тепер таке завдання. Відомо, що на аркуші записано ~k~ рядків чисел. Вам треба знайти максимально можливе натуральне число, яке може бути записане першим у послідовності довжиною ~k~.

Input

Перший рядок містить ~T~ (~1 \le T \le 30~) - кількість тестів. Єдиний рядок кожного тесту містить одне ціле число ~k~ (~2 \le k \le 10^{12}~) - кількість чисел у послідовності

Output

Виведіть для кожного тесту в окремому рядку одне ціле число - найбільше можливе значення початкового числа ~n~. Гарантується, що принаймні одне таке число ~n~ існує та воно є скінченим.

Sample Input 1

3
3
10
100

Sample Output 1

10
17
170

Наша гра відбувається до дошці з ~N~ клітинками, які розташовані в один ряд. На деяких клітинках знаходяться пішаки. Кольори клітинок та пішаків не мають значення: кожен з гравців має право зробити хід будь-яким пішаком, якщо це можливо. Правила ходу пішаком такі ж, як і в звичайних шахах:

• ніякі два пішаки не можуть займати одну і ту ж клітинку;
• пішак не може перестрибувати іншого. Тобто якщо пішак займає клітинку ~i~, то він може переміститися в клітинку ~i - 2~ лише коли клітинки ~i - 1~ та ~i - 2~ є порожніми;
• пішак не може покидати межі дошки.

Гравці ходять по черзі та грають оптимально. При кожному ході гравець має вибрати пішака та перемістити його на одну чи дві клітинки ліворуч від поточного положення. Гравець, який не може зробити хід, програє.

Напишіть програму, яка визначить, чи зможе виграти перший гравець партію при даній розкладці фігур.

Input

Перший рядок містить одне ціле число ~T~ (~1 \le T \le 500~) - кількість тестів.

Кожен тест містить один рядок ~S~ з довжиною ~N~ (~2 \le N \le 128~), що описує розклад фігур. Вільна клітинка позначається '.', а пішак - 'P'

Output

Для кожного тесту виведіть 'Yes' або 'No' в залежності від того, чи виграє перший гравець.

Sample Input 1

1
..P.P

Sample Output 1

Yes

Notes

У прикладі перший гравець переміщає першого пішака ліворуч:

P...P

Другий гравець може ходити лише другим пішаком на одну чи дві клітинки. В будь-якому випадку перший гравець ходить так, що утвориться такий розклад:

PP...

Другий гравець не може зробити хід.

Вам дається послідовність з ~N~ степенів цілого числа ~k~; позначимо ~i~-й член послідовності ~k^{A_i}~. Ви повинні розділити цю послідовність на дві непорожні суміжні підпослідовності; кожен елемент послідовності повинен бути обов'язково в одній із підпослідовностей. Крім цього, добуток суми елементів лівої підпослідовності і суми елементів правої підпослідовності повинен бути максимально можливим.

Ваша програма має знайти найменшу позицію елемента, який поділить послідовність на дві підпослідовності з описаними вимогами. Шуканий елемент буде відноситися до лівої підпослідовності.

Input

Перший рядок містить одне ціле число ~T~ (~1 \le T \le 10~) - кількість тестів.

Далі ідуть тести у наступному форматі:

Перший рядок кожного тесту містить два цілих числа, розділені пропусками ~N~, ~k~ (~2 \le N \le 10^5~, ~2 \le k \le 10^9~).

Другий рядок тесту містить ~N~ цілих чисел, розділених пропусками ~A_1, A_2,…, A_N~ (~0 \le A_i \le 10^5~).

Output

Для кожного тесту виведіть один рядок, що містить одне ціле число - розмір лівої підпослідовності. Якщо є декілька можливих відповідей, виведіть найменшу.

Sample Input 1

1
5 2
1 1 3 3 5

Sample Output 1

4

Notes

Наша послідовність [~2^1,2^1,2^3,2^3,2^5~] = [2,2,8,8,32]. Максимальний добуток ~20 \cdot 32 = 640~. Оптимально послідовність розбивається на [2,2,8,8] і [32].

Забудовник міста розмістив ~n~ будинків вздовж прямолінійної вулиці. Будинок з номером ~i~ знаходиться в точці ~x_i~ і має висоту ~h_i~. Якщо зліва є будинок принаймні у два рази вищий і на відстані не більшій за ~d~, і справа є будинок принаймні у два рази вищий на відстані не більшій за ~d~, то такий будинок за будівельними нормами має недостатню площу прибудинкової території.

Напишіть програму, яка зможе швидко визначити кількість будинків, що мають недостатню прибудинкову територію.

Input

Перший рядок містить розділені пропуском цілі числа ~n~, ~d~ (~1 \le n \le 50 000~, ~1 \le d \le 10^9~).

Далі у ~n~ рядках розміщені ~x_i~ та ~h_i~ (~1 \le x_i,h_i \le 10^9~)

Output

В єдиний рядок вивести одне число - кількість будинків, які мають недостатню прибудинкову територію.

Sample Input 1

6 4
10 3
6 2
5 3
9 7
3 6
11 2

Sample Output 1

2

Notes

Будинки з координатами x = 5 та x = 6 не відповідають будівельним нормам

Компанія DOG International розробила унікального робота-пса із не менш унікальним інтелектом. Робот швидко бігає і при цьому може робити стрибки якої завгодно довжини. Для того, щоб продемонструвати можливості нового робота, розробники поставили науковий експеримент. Робот має рухатися по розміченій прямій. В різних позиціях на прямій знаходиться ~N~ цілей, в яких робот має приземлитися після чергового стрибка(під час експерименту робот буде лише стрибати). Ціль ~i~ розташована у позиції ~x_i~ та має ціну ~p_i~ балів, які зарахуються в актив робота після приземлення у цій позиції.

Робот може почати свій рух із будь-якої позиції, і йому дозволяється рухатися лише в одному напрямку стрибаючи від однієї цілі до іншої. При цьому, кожен наступний стрибок повинен бути зроблений на відстань не меншу за попередню, і приземлятися він має лише у цільових точках. За кожну цільову точку робот отримує відповідні бали включаючи початкову точку.

Яку максимальну кількість балів повинен отримати робот на цих випробуваннях.

Input

Перший рядок містить ціле число ~N~ (~1 \le N \le 1000~) - кількість цільових точок.

Наступні ~N~ рядків містять координату позиції ~x_i~ (~0 \le x_i \le 10^6~) та її ціну ~p_i~ (~0 \le p_i \le 10^6~).

Output

Виведіть максимальну кількість балів, які теоретично можна набрати у таких випробуваннях.

Sample Input 1

6
5 6
1 1
10 5
7 6
4 8
8 10

Sample Output 1

25

Notes

Перший стрибок треба зробити з позиції x = 4 (8 балів) в позицію 5 (6 балів), далі на ціль 7 (6 балів) і в точку 10 (5 балів)