Binary strings are strings that can only have 0 or 1 as the characters. The hash value of a string is calculated using the formula bellow:

Where $n$ is the length of the string, $s_i$ is the $i$’th character of the string and $b$ and $m$ are two positive integers.

For example, let $b=3$ and $m=7$, then “0010” will generate $(0*3^1+0*3^2+1*3^3+0*3^4 ) \mod 7= 27 \mod 7 = 6$ as the hash value.

Given the values of $n$, $m$, $b$ and $h$, your task is to print the lexicographically smallest binary string of length $n$ that will generate $h$ as the hash value.

Input

The input will start with an integer $T(1 \leq T \leq 10^5)$ — the number of test cases.

The next $T$ lines will contain 4 space separated integers $n$, $m$, $b$ and $h$ $(1 \leq n,m,b \leq 10^3; 0 \leq h < m)$ each.

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

Output

For each test case in a line print the lexicographically smallest binary string of length $n$ that generates $h$ as the hash value or print -1 if it doesn’t exist.

Sample

Input	Output
3 2 1 1 0 4 7 3 6 4 37 2 35	00 0010 -1

String $A$ is lexicographically smaller than string $B$  if it is shorter than $B (|A| < |B|)$ and is its prefix, or if none of them is a prefix of the other and at the first position where they differ, the character in $A$ is smaller than the character in $B$.