B. Fair Numbers | Codeforces | Technocup 2021 - Elimination Round 3 | Solution

We call a positive integer number fair if it is divisible by each of its nonzero digits. For example, 102 is fair (because it is divisible by 1 and 2 ), but 282 is not, because it isn't divisible by 8 . Given a positive integer 𝑛 . Find the minimum integer 𝑥 , such that 𝑛≤𝑥 and 𝑥 is fair.

B. Fair Numbers

Time limit per test: 2 seconds

Memory limit per test: 256 megabytes

Problem Statement

We call a positive integer number fair if it is divisible by each of its nonzero digits. For example, 102 is fair (because it is divisible by 1 and 2), but 282 is not, because it isn't divisible by 8. Given a positive integer n, find the minimum integer x, such that n ≤ x and x is fair.

Input

The first line contains an integer t (1 ≤ t ≤ 10³), the number of test cases.
Each of the next t lines contains an integer n (1 ≤ n ≤ 10¹⁸).

Output

For each test case, print a single integer — the least fair number, which is not less than n.

Example

Input

4
1
282
1234567890
1000000000000000000

Output

1
288
1234568040
1000000000000000000

Note

Explanations for some test cases:

In the first test case, number 1 is fair itself.
In the second test case, number 288 is fair (it's divisible by both 2 and 8). None of the numbers from [282,287] is fair.

Hint

A super-fair number is a number that is divisible by every digit from 1 to 9. Since these numbers are also divisible by the least common multiple: LCM(1..9) = 2520, we can use this property to optimize our search. Instead of checking every number sequentially, we increment n until we find a number that is divisible by all its nonzero digits. This guarantees that our answer won’t exceed the nearest super-fair number.

bool helper2(int n){
  string s = to_string(n);
  for(auto c:s){
    int i = c-'0';
    if(i>0){
      if(n%i!=0)return false;
    }
  }
  return true;
}
 
void solve() {
 
int n;
cin>>n;
 
while(true){
  if( helper2(n)){
    cout<<n<<endl;
    return;
  }
  n++;
  if(n%2520 == 0){
    cout<<n<<endl;
    return;
  }
}
}

Solution Explanation

The goal is to find the smallest fair number x such that x ≥ n and x is divisible by all of its nonzero digits. The solution uses a brute-force approach with an important optimization.

Checking Fairness

The helper2(n) function determines if a number is fair:

Convert n into a string and iterate over its digits.
Ignore 0 to avoid division errors.
If any nonzero digit does not divide n evenly, return false.
If all nonzero digits divide n, return true.

Finding the Smallest Fair Number

The algorithm starts from n and increments it until it finds a fair number.

If n is fair, print it and return.
Otherwise, increment n and check again.
If n becomes a multiple of 2520 (the LCM of 1 to 9), print it immediately.

Optimization Using LCM

Since every **super-fair number** is divisible by **2520**, the algorithm is optimized by checking if n is a multiple of 2520:

If n reaches a multiple of 2520, we print it immediately.
This skips unnecessary iterations and speeds up the solution.

Time Complexity

- In the worst case, the algorithm increments n a few times until it finds a fair number.
- Thanks to the 2520 optimization, it runs efficiently for large values of n.

Complete Code

#include <bits/stdc++.h>

using namespace std;

#define int            long long int
#define F              first
#define S              second
#define pb             push_back
#define si             set <int>
#define vi             vector <int>
#define pii            pair <int, int>
#define vpi            vector <pii>
#define vpp            vector <pair<int, pii>>
#define mii            map <int, int>
#define mpi            map <pii, int>
#define spi            set <pii>
#define endl           "\n"
#define sz(x)          ((int) x.size())
#define all(p)         p.begin(), p.end()
#define double         long double
#define que_max        priority_queue <int>
#define que_min        priority_queue <int, vi, greater<int>>
#define bug(...)       __f (#__VA_ARGS__, __VA_ARGS__)
#define print(a)       for(auto x : a) cout << x << " "; cout << endl
#define print1(a)      for(auto x : a) cout << x.F << " " << x.S << endl
#define print2(a,x,y)  for(int i = x; i < y; i++) cout<< a[i]<< " "; cout << endl
#define scanit(a,n) for(ll indexaa=0; indexaa<n; indexaa++) cin>>a[indexaa];

inline int power(int a, int b)
{
  int x = 1;
  while (b)
  {
    if (b & 1) x *= a;
    a *= a;
    b >>= 1;
  }
  return x;
}

template <typename Arg1>
void __f (const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << endl; }
template <typename Arg1, typename... Args>
void __f (const char* names, Arg1&& arg1, Args&&... args)
{
  const char* comma = strchr (names + 1, ',');
  cout.write (names, comma - names) << " : " << arg1 << " | "; __f (comma + 1, args...);
}

const int N = 200005;


bool helper2(int n){
  string s = to_string(n);
  for(auto c:s){
    int i = c-'0';
    if(i>0){
      if(n%i!=0)return false;
    }
  }
  return true;
}

void solve() {

int n;
cin>>n;

while(true){
  if( helper2(n)){
    cout<<n<<endl;
    return;
  }
  n++;
  if(n%2520 == 0){
    cout<<n<<endl;
    return;
  }
}



}

int32_t main()
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);


  clock_t z = clock();

  int t = 1;
  cin >> t; 
  while (t--) solve();



  return 0;
}