Problem: You are given two positive integers d and s. Find minimal positive integer n which is divisible by d and has sum of digits equal to s.

Input

The first line contains two positive integers d and s (1 ≤ d ≤ 500, 1 ≤ s ≤ 5000) separated by space.

Output

Print the required number or -1 if it doesn't exist.

Examples

Input

13 50


Output

699998


Input

61 2


Output

1000000000000000000000000000001


Input

15 50


Output

-1

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline bool chkmin(T &a, T b) {
  return b < a ? a = b, 1 : 0;
}
template <typename T>
inline bool chkmax(T &a, T b) {
  return b > a ? a = b, 1 : 0;
}
inline int read() {
  int x(0), sgn(1);
  char ch(getchar());
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') sgn = -1;
  for (; isdigit(ch); ch = getchar()) x = (x * 10) + (ch ^ 48);
  return x * sgn;
}
void File() {}
const int N = 510;
bool app[N][5010];
pair<int, int> pre[N][5010];
void Out(pair<int, int> sta) {
  if (sta.first == 0 && sta.second == 0) return;
  Out(pre[sta.first][sta.second]);
  printf("%d", sta.second - pre[sta.first][sta.second].second);
}
int main() {
  File();
  int n = read(), s = read();
  queue<pair<int, int> > Q;
  Q.push(make_pair(0, 0));
  if (s == 0) return puts("-1"), 0;
  while (!Q.empty()) {
    pair<int, int> cur = Q.front();
    Q.pop();
    app[cur.first][cur.second] = true;
    if (cur.first == 0 && cur.second == s) {
      Out(cur);
      return 0;
    }
    for (register int i = (0), iend = (int)(9); i <= iend; ++i) {
      pair<int, int> nxt = make_pair((cur.first * 10 + i) % n, cur.second + i);
      if (!app[nxt.first][nxt.second] && nxt.second <= s) {
        app[nxt.first][nxt.second] = true;
        Q.push(nxt);
        pre[nxt.first][nxt.second] = cur;
      }
    }
  }
  puts("-1");
  return 0;
}