Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^5$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 10^6$).

The second line contains a string of $n$ digits $d_0 d_1 \ldots d_{n-1}$ ($0 \le d_i \le 9$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$.