Каждый тест содержит несколько тестовых случаев. Первая строка содержит количество тестов $t$ ($1 \le t \le 10^5$). Далее следует описание тестовых случаев.

Первая строка каждого теста содержит одно целое число $n$ ($1 \le n \le 10^6$).

Вторая строка содержит строку из $n$ цифр $d_0 d_1 \ldots d_{n-1}$ ($0 \le d_i \le 9$).

Гарантируется, что сумма $n$ по всем наборам входных данных не превосходит $10^6$.