C. Raspberries Solution | Codeforces Round 905 (Div. 3)

You are given an array of integers 𝑎1,𝑎2,…,𝑎𝑛 and a number 𝑘 (2≤𝑘≤5 ). In one operation, you can do the following: Choose an index 1≤𝑖≤𝑛 , Set 𝑎𝑖=𝑎𝑖+1 . Find the minimum number of operations needed to make the product of all the numbers in the array 𝑎1⋅𝑎2⋅…⋅𝑎𝑛 divisible by 𝑘 .

C. Raspberries

You are given an array of integers a₁, a₂, ..., a_n and a number k (2 ≤ k ≤ 5). In one operation, you can:

Choose an index 1 ≤ i ≤ n.
Set a_i = a_i + 1.

Find the minimum number of operations needed to make the product P = a₁ ⋅ a₂ ⋅ ... ⋅ a_n divisible by k.

Input

Each test consists of multiple test cases.

The first line contains a single integer t (1 ≤ t ≤ 10⁴) — the number of test cases.
Each test case starts with two integers n and k (2 ≤ n ≤ 10⁵, 2 ≤ k ≤ 5).
The second line contains n integers a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10).

It is guaranteed that the sum of all n over all test cases does not exceed 2 × 10⁵.

Output

For each test case, output the minimum number of operations needed to make the product divisible by k.

Example

Input
15
2 5
7 3
3 3
7 4 1
5 2
9 7 7 3 9
5 5
5 4 1 2 3
7 4
9 5 1 5 9 5 1
3 4
6 3 6
3 4
6 1 5
3 4
1 5 9
4 4
1 4 1 1
3 4
3 5 3
4 5
8 9 9 3
2 5
1 6
2 5
10 10
4 5
1 6 1 1
2 5
7 7

Output
2
2
1
0
2
0
1
2
0
1
1
4
0
4
3

Explanation

Test Case 1: Choose index i = 2 twice. After that, the array becomes a = [7, 5], and 7 × 5 = 35, which is divisible by 5.

Test Case 4: The product is already divisible by 4, so no operations are needed.

Test Case 8: We can perform two operations by choosing i = 2 and i = 3. After that, the array is a = [1,6,10], and 1 × 6 × 10 = 60, which is divisible by 4.

void solve()
{

    int n, k;
    cin >> n >> k;
    int ans = INT_MAX;
    vi v(n);
    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
        int x = v[i] % k;
        if (x != 0)
            ans = min(ans, k - x);
        else
            ans = 0;
    }

    if (k == 4)
    {
        int cnt = 0;
        for (auto i : v)
            if (i % 2 == 0)
                cnt++;
        if (cnt >= 2)
        {
            ans = 0;
        }
        else
            ans = min(ans, 2 - cnt);
    }

    cout << ans << endl;
}


#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;

void solve()
{

    int n, k;
    cin >> n >> k;
    int ans = INT_MAX;
    vi v(n);
    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
        int x = v[i] % k;
        if (x != 0)
            ans = min(ans, k - x);
        else
            ans = 0;
    }

    if (k == 4)
    {
        int cnt = 0;
        for (auto i : v)
            if (i % 2 == 0)
                cnt++;
        if (cnt >= 2)
        {
            ans = 0;
        }
        else
            ans = min(ans, 2 - cnt);
    }

    cout << ans << endl;
}

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;
}

TagsC. RaspberriesCodeforces Round 905 (Div. 3)Raspberries Solution CodeForcesproblem solving techniquesweb developmenttailwind css examplescoding problem solutionsprogramming contestsnumber theory problemscoding interview questionsalgorithm challengescodeforces problemcompetitive programming

Raunit Verma

Technical Writer at CodingKaro

Share this on