Description

Ysuperman’s kindergarten not only focuses on cultural classes and competitive programming classes, but also teaches everyone to develop morally, intellectually, physically, and aesthetically. One weekend, the well-rounded Ysuperman climbed Mount Y.

When climbing, Ysuperman did not take the main road for vehicles, but instead took the muddy trail beside it. After walking for a long time, he suddenly found that the way back had become blurry, and in front of him stood a huge rock wall. To his shock, he discovered that the wall actually had writings from the last century! “义已失吾亦死”. Looking at these words, he seemed to feel a special kind of charm.

After returning to kindergarten, the excited Ysuperman immediately created other sentences, but found that most of them had lost their charm. After two and a half years of research, TA finally discovered that “义已失吾亦死” actually corresponds to the number string $114514$! With a clearer direction, he decided to study mapping a sentence to a number. A “charming” number must satisfy the following conditions:

• In decimal, it is a natural number.

• Its digits only contain the three digits $1,4,5$.

• It is congruent to $0$ modulo a given constant $p$.

Now Ysuperman already has many digits $1,4,5$, with $a_1,a_4,a_5$ of them respectively.

Ysuperman wants to form a charming number of length $n$ that is as large as possible.

Ysuperman knows that if TA were still a student, TA would surely qualify for the Hydroxyl Program because of this discovery. For TA’s childhood dream, can you help him?

Input Format

This problem contains multiple test cases.

There are $T$ test cases. The first line contains $T$. Then for each test case:

The first line contains two positive integers $n,p$, representing the length of the charming number Ysuperman wants to form and the given constant $p$.

The second line contains three natural numbers $a_1,a_4,a_5$, representing the initial counts of digits that Ysuperman has.

Output Format

If Ysuperman cannot obtain a charming number, output -1.

Otherwise, output the maximum charming number Ysuperman can form.

A newline is required between two test cases.

5
1 1
1 1 1
3 5
1 1 2
6 62
3 2 1
23 13
10 10 10
233 10
233 233 233

5
545
114514
55555555554444444441111
-1

5
100 64
33 33 34
114 63
33 33 50
115 62
111 11 1
192 60
8 1 7
233 64
100 100 33

5555555555555555555555555555555555444444444444444444444444444441111111111111111111111111111111414144
555555555555555555555555555555555555555555555555444444444444444444444444444444441111411111111111111111111111111111
5444444444111111111114111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111114
-1
55555555555555555555555555555555544444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444411111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111414144

Hint

Sample Explanation

Sample Explanation $1$:

In the first test case, you can form $1,4,5$, and the maximum is $5$.

In the second test case, you can form $145,155,415,455,515,545$, and the maximum is $545$.

In the third test case, you can only form $114514$.

Constraints

To pay tribute to NOI, the problem setter specially prepared a generous partial score table.

Property 1: $a_1+a_4+a_5=n$.

Property 2: $a_1=a_4=a_5=n$.

For $100\%$ of the testdata, it holds that:

$0 \le a_1,a_4,a_5 \le 233$.
$1 \le n \le 233$.
$1 \le p \le 64$.
$0 \le T \le 5$.

Hint

If you do not know what a natural number means, Ysuperman provides a link: link.

If you do not know what modulo means, Ysuperman provides another link: link。

Translated by ChatGPT 5