Розв’яжіть наступну задачу для \(T\) тестових випадків.

Фігура розміщується в початку координат (0, 0) на площині xy. Ви можете виконати наступну операцію будь-яку кількість (можливо, нуль) разів:

• Виберіть таке ціле число \(i\), щоб \(1 \leq i \leq 8\) і \(s_i=\) 1. Нехай (\(x, y\)) є поточними координатами, де розміщено фігуру.

  • Якщо \(i=1\), перемістіть фігуру до (\(x+1,y\)).
  • Якщо \(i=2\), перемістіть фігуру до (\(x+1,y+1\)).
  • Якщо \(i=3\), перемістіть фігуру до (\(x,y+1\)).
  • Якщо \(i=4\), перемістіть фігуру до (\(x-1,y+1\)).
  • Якщо \(i=5\), перемістіть фігуру до (\(x-1,y\)).
  • Якщо \(i=6\), перемістіть фігуру до (\(x-1,y-1\)).
  • Якщо \(i=7\), перемістіть фігуру до (\(x,y-1\)).
  • Якщо \(i=8\), перемістіть фігуру до (\(x+1,y-1\)).

Ваше завдання — перемістити фігуру в (\(A, B\)).

Знайдіть мінімальну кількість операцій, необхідних для досягнення мети. Якщо це неможливо, замість цього виведіть -1.

Обмеження

• \(1 \leq T \leq 10^4\)
• \(-10^9 \leq A,B \leq 10^9\)
• \(s_i\) дорівнює 0 або 1.
• \(T\), \(A\) і \(B\) — цілі числа.

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

Вхідні дані надаються зі стандартного вводу в такому форматі:

T
case 1
​case 2 
⋮
case T

​ Кожен тест \(case i\) надається в такому форматі:

A B s_1s_2s_3s_4s_5s_6s_7s_8

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

У вихідний потік виведіть \(T\) рядків. \(I\)-й рядок має містити відповідь на \(i\)-й тест.

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

7
5 3 10101010
5 3 01010101
5 3 11111111
5 3 00000000
0 0 11111111
0 1 10001111
-1000000000 1000000000 10010011

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

8
5
5
-1
0
-1
1000000000