A. k-rounding

time limit per test:1 second

memory limit per test:256 megabytes

input:standard input

output:standard output

For a given positive integer n denote its k-rounding as the minimum positive integer x, such that x ends with k or more zeros in base 10 and is divisible by n.

For example, Pawnchess of 375 is 375·80 = 30000. Chess is the minimum integer such that it ends with 4 or more zeros and is divisible by 375.

Write a program that will perform the k-rounding of n.

Input

The only line contains two integers n and k (1 ≤ n ≤ 109, 0 ≤ k ≤ 8).

Output

Print the k-rounding of n.

Examples

Input

375,Copy the code

Output

30000
Copy the code

Input

10000 1
Copy the code

Output

10000
Copy the code

Input

38101 0
Copy the code

Output

38101
Copy the code

Input

123456789 8
Copy the code

Output

12345678900000000
Copy the code

Title links: codeforces.com/contest/861…

X has more than K 0’s at the end of it; And x is a multiple of n, x over 10 to the k is a multiple of n, x is a multiple of 10 to the k

Here is the AC code:

1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 ll gcd(ll a,ll b) 5 { 6 return b==0? a:gcd(b,a%b); 7 } 8 int main(void) 9 { 10 ll n,k; 11 cin>>n>>k; 12 ll temp=1; 13 for(ll i=1; i<=k; i++) 14 temp*=10; 15 cout<<n*temp/gcd(temp,n); 16}Copy the code