Розглянемо узагальнений опис послідовності Фібоначчі, у якій два перші елементи ~F1~ та ~F2~ визначаються довільно.

Ваше завдання: знайти кількість простих чисел у першій двадцятці членів цієї послідовності

Формат вхідних даних

Перший рядок вхідного потоку містить ~T~ (~1 \le T \le 2\cdot10^5~) - кількість тестів.

Далі ідуть тести. Кожен тест в окремому рядку містить два цілих числа ~F1~, ~F2~ (~2 \le F1,F2 \le 100~), які розділені пропуском.

Формат вихідних даних

Для кожного вхідного тесту вивести в окремому рядку кількість простих чисел в утвореній послідовності Фібоначчі.

Приклад вхідних даних

1
100 37

Приклад вихідних даних

4

У нас є ~N~ діжок різної висоти. В ~i~-у діжку неможливо налити більше води, ніж її висота. Нам треба заповнити діжки таким чином, щоб висота води в (~i+1~)-й діжці була на ~K~ більше, ніж висота води, яку залили в ~i~-у діжку, для ~1 \le i \le N-1~.

Необхідно знайти максимально можливе значення ~K~ і максимальну початкову висоту води ~H~.

Якщо ~N~ = 1, то потрібно заповнити цей контейнер до верху, а значення ~K~ буде ~H_1-1~.

В загальному випадку перший контейнер повинен бути заповнений принаймні до висоти 1.

Формат вхідних даних

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

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

Перший рядок кожного тесту - N (~1 \le N \le 10^5~) - кількість наявних діжок.

Другий рядок тесту містить ~N~ цілих чисел, розділених пропуском ~H_i~ (~1 \le H_i \le 10^{12}~) - висоти відповідних діжок.

В одному тесті кількість всіх чисел не перевищує ~10^5~.

Формат вихідних даних

Для кожного тесту в окремому рядку вивести через пропуск ~K~ та ~H~

Примітка

Для першого тесту оптимальне наповнення діжок буде при максимальному K = 49 і максимальній висоті 2. Наповнення діжок буде таким: 2, 51, 100.

У другому тесті маємо лише одну діжку, тому максимальне значення K = 7, а максимальна початкова висота рівна 8.

Приклад вхідних даних

2
3
200 150 100
1
8

Приклад вихідних даних

49 2
7 8

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

Назар витрачає ~B~ одиниць енергії на перехід з одного пункту до сусіднього, а Юля витрачає ~E~ одиниць. Якщо Назар та Юля випадково опиняться в одному пункті, то Назар зможе понести Юлю на руках (якщо це буде енергетично вигідно), витративши ~P~ одиниць енергії для переміщення у сусідній пункт (~P~ може бути меншим ніж ~B + E~).

За заданим ~B~, ~E~, ~P~ і розташуванням пунктів, обчисліть мінімальну кількість енергії, яка буде потрібна Назару та Юлі щоб повернутися на базу.

Формат вхідних даних

Перший рядок містить додатні числа ~B~, ~E~, ~P~, ~N~, ~M~, які не перевищують 40000. ~N~ - кількість пунктів, пронумерованих від 1 до ~N~, (~3 \le N~). ~M~ - кількість шляхів між пунктами. Назар та Юля знаходяться на початку в пунктах 1 і 2 відповідно. База розташована в пункті ~N~.

Кожен з наступних ~M~ рядків описує шлях між пунктами. Шляхи двонаправлені. Завжди існує шлях від пункту 1 до пункту ~N~ і від пункту 2 до пункту ~N~.

Формат вихідних даних

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

Приклад вхідних даних

4 4 5 8 8 1 4 2 3 3 4 4 7 2 5 5 6 6 8 7 8

Приклад вихідних даних

22

У нас є два рядки ~S~ і ~P~, причому ~P~ є підрядком рядка ~S~. Рядки містять лише малі англійські символи. Ваша програма має виконати ~Q~ запитів над підрядком ~S~. Кожен запит містить ціле додатне ~N~ та символ нижнього регістру ~C~. Для кожного запиту ~Q_i~ треба замінити символ з індексом ~N~ (індекси починаються з 0) рядка ~S~ на символ ~C~. Запити виконуються у порядку їх слідування. Вам треба знайти мінімальну кількість запитів для того, що ~P~ перестав бути підрядком ~S~.

Якщо рядок ~P~ буде підрядком ~S~ навіть після виконання всіх запитів ~Q~, тоді треба вивести -1.

Формат вхідних даних

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

Перший рядок кожного тесту містить один рядок ~S~ (~1 \le |S| \le 2\cdot10^5~).

Другий рядок кожного тесту містить один рядок ~P~ (~1 \le |P| \le |S|~)

Третій рядок кожного тесту містить одне ціле число ~Q~ (~1 \le Q \le |S|~) - кількість запитів.

Наступні рядки Q тесту містять ~N~ (~0 \le N \le |S|~) і ~C~, які розділені пропуском.

Формат вихідних даних

Для кожного тесту вивести відповідну відповідь.

Приклад вхідних даних

2
abcdefg
bc
3
0 d
1 q
2 z
abcdefg
cde
2
0 z
1 k

Приклад вихідних даних

2
-1