(RGS 1/5) Binary multiples A binary multiple of a positive integer k is a positive integer n such that n is written only with 0s and 1s in base 10 and n is a multiple of k. For example, 111111 is a binary multiple of 3.

It is easy to show that a positive integer has infinitely many binary multiples. See here for a construction proof of one binary multiple for each k. Multiplying by powers of 10 you get infinitely many more.

Your task

Given a positive integer k, return the smallest binary multiple of k.

Input

A positive integer k.

Output

A positive integer n, the smallest binary multiple of k.

Test cases

2 -&gt; 10
3 -&gt; 111
4 -&gt; 100
5 -&gt; 10
6 -&gt; 1110
7 -&gt; 1001
8 -&gt; 1000
9 -&gt; 111111111
10 -&gt; 10
11 -&gt; 11
12 -&gt; 11100
13 -&gt; 1001
14 -&gt; 10010
15 -&gt; 1110
16 -&gt; 10000
17 -&gt; 11101
18 -&gt; 1111111110
19 -&gt; 11001
20 -&gt; 100
100 -&gt; 100


This is code-golf so shortest submission in bytes, wins! If you liked this challenge, consider upvoting it... And happy golfing!



This is the first challenge of the RGS Golfing Showdown. If you want to participate in the competition, you have 96 hours to submit your eligible answers. Remember there is 450 reputation in prizes! (See 6 of the rules)

Otherwise, this is still a regular code-golf challenge, so enjoy!
05AB1E, 6 bytes
∞b.ΔIÖ

Try it online! or verify all test cases (courtesy of @KevinCruijssen)

Explanation
∞b           - Infinite binary list
  .Δ         - Find the first value such that..
    IÖ       - It's divisible by the input