Given an integer $n$ and a binary sequence $a_2, a_3, \dots, a_{n-1}$ of length $n-2$, construct an undirected simple connected graph $G$ with $n$ vertices such that:

• Vertex $1$ is an articulation point, and vertex $n$ is not an articulation point.
• For each $1 < i < n$:
  • If $a_i = 1$, then vertex $i$ is an articulation point in $G$.
  • If $a_i = 0$, then vertex $i$ is not an articulation point in $G$.
• The degrees of the vertices in $G$ satisfy: $\deg_1 \ge \deg_2 \ge \dots \ge \deg_n$.

If there are multiple possible graphs, output any one. If no such graph exists, output $-1$.

A simple graph is defined as a graph with no multiple edges (at most one edge between any pair of vertices) and no self-loops (no edge connecting a vertex to itself).

An articulation point is defined as a vertex whose removal, along with its incident edges, increases the number of connected components in the graph.

Input

This problem contains multiple test cases. The first line contains an integer $T$ ($1 \le T \le 500$), representing the number of test cases. For each test case: The first line contains an integer $n$ ($4 \le n \le 1000$), representing the number of vertices in the graph. The next line contains a binary string of length $n-2$, representing the sequence $a_2, a_3, \dots, a_{n-1}$. It is guaranteed that the sum of $n$ over all test cases does not exceed $2000$.

Output

For each test case: If there is no solution, output $-1$. If there is a solution, first output $m$ ($0 < m \le \frac{n(n-1)}{2}$), representing the number of edges in the graph. Then output $m$ lines, each containing two integers, where the $i$-th line contains the indices of the two endpoints of the $i$-th edge. If there are multiple graphs satisfying the requirements, you may output any one.

Examples

Input 1

2
4
11
7
11000

Output 1

-1
6
1 2
1 3
1 4
2 5
2 6
3 7

Note

For the first example, it can be proven that no graph satisfying the requirements exists. For the second example, the graph is as follows:

In this graph, vertices $1, 2, 3$ are articulation points, and $\deg_1 \sim \deg_7$ are $3, 3, 2, 1, 1, 1, 1$, which satisfies the requirements.