Skip to content
TheChatArchiveThe Chat Archive
DeepSeekDeepseek v3.2· deepseekHugging Face Frontier Reasoning Traces

You are given two integers n and k. You should create an array of n positive integers…

  1. User

    You are given two integers n and k.

    You should create an array of n positive integers a_1, a_2, ..., a_n such that the sum (a_1 + a_2 + ... + a_n) is divisible by k and maximum element in a is minimum possible.

    What is the minimum possible maximum element in a? Input

    The first line contains a single integer t (1 ≤ t ≤ 1000) — the number of test cases.

    The first and only line of each test case contains two integers n and k (1 ≤ n ≤ 10^9; 1 ≤ k ≤ 10^9).

    Output

    For each test case, print one integer — the minimum possible maximum element in array a such that the sum (a_1 + ... + a_n) is divisible by k.

    Example

    Input

    4 1 5 4 3 8 8 8 17

    Output

    5 2 1 3

    Note

    In the first test case n = 1, so the array consists of one element a_1 and if we make a_1 = 5 it will be divisible by k = 5 and the minimum possible.

    In the second test case, we can create array a = [1, 2, 1, 2]. The sum is divisible by k = 3 and the maximum is equal to 2.

    In the third test case, we can create array a = [1, 1, 1, 1, 1, 1, 1, 1]. The sum is divisible by k = 8 and the maximum is equal to 1.

  2. DeepSeek Assistant

    We need to interpret the problem: Given n and k, we need to choose n positive integers (>=1) such that the sum S = sum(a_i) is divisible by k. We want to minimize the maximum element among the a_i. Let M = max a_i. We want the minimal possible M that can be achieved with some array of n positive integers whose sum is divisible by k.

    Observations: We can choose any numbers as long as they are positive integers. We want to keep them as small as possible, but we need the sum to be divisible by k. The minimal sum if we set all a_i = 1 is n. But n mod k might not be 0. To achieve divisibility, we need to increase the sum by some amount (by increasing some elements) so that the total sum becomes a multiple of k. However, we could also possibly decrease? No, because all numbers are at least 1, so minimal sum is n. So the sum must be >= n. To achieve divisibility by k, we need S ≡ 0 mod k, and S >= n. The minimal S >= n that is ≡ 0 mod k is: if n % k == 0, then S = n works; otherwise, we need S = n + (k - n % k). Because the next multiple of k greater than or equal to n is ceil(n/k)*k = n + (k - n%k) if n%k !=0.

    So the minimal total sum that we can achieve (subject to the constraint that all a_i >=1) is S_min = ceil(n/k)*k. But wait: is it always possible to achieve that sum with an array of n positive integers whose maximum element is as low as possible? Possibly we need to distribute the extra sum (S_min - n) among some elements, increasing them. We want to minimize the maximum element. We start with all ones: each is 1. Then we need to add D = S_min - n to the sum, distributed over the n elements (increase some elements). The increases must be integer increments, because final numbers must be integers. We can add any nonnegative integer amounts to each element, but we want to minimize the maximum after adding.

    This is similar to: we have n numbers initially 1. We need to add total D to the sum, and we can add to each element any integer amount ≥0. After adding, the maximum value among the numbers (which is 1 plus the max added amount) should be as small as possible. The optimal strategy to minimize the max while distributing D among n bins is to spread D as evenly as possible: so each element gets either floor(D/n) or ceil(D/n) extra. Then the maximum after addition is 1 + ceil(D/n). However, is there any additional constraint? For instance, could we possibly achieve a smaller maximum by not using the minimal total sum? Maybe using a larger sum (e.g., next multiple of k) could allow a smaller maximum? Let's examine: if we take a larger sum, then D is larger, which would increase the maximum (since we have to distribute more). But maybe we can choose a sum that is not minimal but we can keep the maximum lower by using a different distribution? That seems contradictory: increasing sum means we need to increase numbers more, so max can only increase or stay same? Not necessarily: Suppose we have n=1, k=5. Minimal sum is 5 (since ceil(1/5)*5=5). So M = 5. If we instead take S = 10, then a1=10, M=10, bigger. So minimal sum gives smallest max? Possibly not always: consider n=3, k=5. Minimal sum >=3 that is multiple of 5 is 5. D = 2. n=3. Spread 2 among 3 elements: we can increase two elements by 1 each, resulting array: [2,2,1] max=2. ceil(D/n)=ceil(2/3)=1, so max = 2. Could we do better by using sum=10? D=7, ceil(7/3)=3, max=4 >2. So minimal sum seems better.

    But consider n=4, k=3. Minimal sum: n=4, next multiple of 3 is 6 (since 4%3=1, need +2). D=2. Spread among 4: ceil(2/4)=1, so max=2. Indeed example output is 2. Works.

    Now consider n=8, k=8: n%k=0, D=0, max=1. Works.

    Now n=8, k=17: n=8, next multiple of 17 is 17, D=9. Spread among 8: ceil(9/8)=2? Actually 9/8=1.125, ceil=2, so max=1+2=3. Output is 3. Works.

    So pattern seems to be: answer = ceil(n/k) if? Let's derive: S_min = ceil(n/k)*k, D = S_min - n, max = 1 + ceil(D/n). But we can simplify:

    Let q = floor(n/k) or ceil? Actually, let's denote t = ceil(n/k). Then S_min = t * k. D = tk - n. Then answer M = 1 + ceil((tk - n)/n). Compute: ceil((tk - n)/n) = ceil(tk/n - 1) = ceil(tk/n) - 1? Not exactly because ceil(x - 1) = ceil(x) - 1 if x not integer? Let's derive: ceil(tk/n - 1) = ceil(tk/n - 1). In general, ceil(A - 1) = ceil(A) - 1 if A is not integer? Actually, for any real number A, ceil(A - 1) = ceil(A) - 1. Because ceil(A - 1) = smallest integer >= A-1 = smallest integer >= A - 1. If we let m = ceil(A), then m-1 < A <= m, so (m-1)-1 < A-1 <= m-1, i.e., m-2 < A-1 <= m-1. The smallest integer >= A-1 is m-1 if A-1 is not integer? But more formally: Since ceil(A) = m, we have m-1 < A <= m. Then A-1 <= m-1 and A-1 > m-2. So the smallest integer >= A-1 is m-1 (because m-1 >= A-1? Actually, need check if A-1 could be exactly integer: If A is integer, then A = m, then A-1 = m-1 which is integer, and ceil(m-1)=m-1, which is m-1 = ceil(A)-1. So formula holds: ceil(A-1) = ceil(A)-1. Good. So ceil(tk/n - 1) = ceil(tk/n) - 1. Thus M = 1 + (ceil(tk/n) - 1) = ceil(t*k/n).

    So answer simplifies to M = ceil( (t * k) / n ) where t = ceil(n/k).

    But t = ceil(n/k). Then t*k is the minimal multiple of k that is >= n. So M = ceil( (smallest multiple of k >= n) / n ). Let S0 = smallest multiple of k >= n. Then M = ceil(S0 / n). That's a neat expression.

    But we can also think in terms of: The minimal possible maximum element is the smallest integer m such that there exists an array of n positive integers each ≤ m with sum divisible by k. Equivalent to: we need to achieve sum multiple of k using numbers between 1 and m inclusive. The smallest sum we can achieve with those constraints is n (all 1's). The largest sum is nm (all m's). For divisibility, we need some sum in [n, nm] that is multiple of k. The minimal m for which there exists a multiple of k in that interval is what we need. Because we can adjust numbers arbitrarily between 1 and m to get any sum from n to nm (maybe not all, but we can achieve any integer? For given m and n, the set of achievable sums using n numbers each between 1 and m is all integers from n to nm, because we can increment one element at a time. Yes, the range is contiguous: start with all 1's sum=n, then you can increase any element by 1 up to m, so you can reach any sum up to nm. Actually, it's possible to achieve any integer between n and nm inclusive because you can start from all 1's and increase one by one; each increment increases sum by 1, so all sums are reachable. So the condition is: There exists an integer S such that S is multiple of k and n ≤ S ≤ nm. The minimal m is the smallest integer such that the interval [n, nm] contains a multiple of k.

    Thus answer = minimal m >=1 such that ceil(n/k)k ≤ nm? Wait: The smallest multiple of k >= n is S0 = ceil(n/k)k. If S0 ≤ nm, then the interval contains that multiple. So condition: n*m >= S0 => m >= ceil(S0 / n). So minimal integer m = ceil(S0 / n). And indeed that matches the derived expression.

    Thus answer = ceil( ceil(n/k) * k / n ) = ceil( (k * ceil(n/k)) / n ).

    We can also simplify further. Let r = n mod k. If r == 0, then n is multiple of k, so ceil(n/k) = n/k, S0 = n, answer = ceil(n / n) = 1. Good.

    If r != 0, then n = q*k + r with 0 < r < k. Then ceil(n/k) = q+1. S0 = (q+1)*k. Then M = ceil( (q+1)k / (qk + r) ). This might be something like: M = ceil( (q+1)*k / n ). Let's compute: (q+1)k = kq + k = n - r + k = n + (k - r). So M = ceil( (n + (k - r)) / n ) = ceil( 1 + (k - r)/n ) = 1 + ceil( (k - r)/n )? But careful: ceil(1 + x) = 1 + ceil(x) if x is not integer? Actually ceil(1 + x) = 1 + ceil(x) for any real x because adding 1 shifts both integer part and fractional part. So M = 1 + ceil( (k - r) / n ). But (k - r) < k ≤ 1e9, and n can be large. However, note that (k - r) is the deficit to next multiple. But earlier we had M = 1 + ceil(D/n) with D = S0 - n = (k - r). Indeed D = k - r. So M = 1 + ceil( (k - r) / n ). That's consistent with initial thought.

    But we can also simplify to M = floor( (n + k - 1) / n )? Not exactly. Let's test for n=4,k=3: n=4, k=3, r=1, k-r=2, ceil(2/4)=1, M=2. OK. For n=8,k=17: n=8, k=17, r=8? Actually n=8, k=17: n mod k = 8 (since 8<17), r=8, k-r=9, ceil(9/8)=2, M=3. OK.

    So the answer is simply: if n % k == 0: 1; else: Let d = k - (n % k). Then answer = 1 + ceil(d / n). But can we simplify ceil(d/n)? Since d < k and n could be huge, d/n is less than 1 unless n ≤ d? Actually d could be greater than n? For n=1,k=5: d = 5 - 1 =4? Wait n%k = 1%5 =1, d=4. ceil(4/1)=4, M=5. That matches. For n=2,k=3: n=2, r=2, d=1, ceil(1/2)=1, M=2. Let's test: n=2,k=3: Need sum divisible by 3, minimal sum≥2: S0=3, D=1, spread among 2, ceil(1/2)=1, so M=2. Is that optimal? Could we achieve max=1? If both 1, sum=2 not divisible by 3. Can't. So M=2. Works.

    Now consider n=100, k=100: n%k=0 => 1.

    Now consider n=10^9, k=1: then n%k=0 => answer=1. That makes sense: any sum divisible by 1, we can set all ones.

    Now consider n=1, k=1: answer=1.

    Now consider n=5, k=3: n=5, r=2, d=1, ceil(1/5)=1, M=2. Check: S0=6, D=1, spread among 5 gives max=2 (one element becomes 2, rest 1). Is that possible? Yes, array [2,1,1,1,1] sum=6 divisible by 3, max=2. Could we do max=1? Sum would be 5, not divisible by 3. So answer 2.

    Now consider n=5, k=7: n=5, r=5, d=2, ceil(2/5)=1, M=2. S0=7, D=2, spread: e.g., [2,2,1,1,1] sum=7, max=2. Could we do max=1? Sum=5 not multiple of 7, need at least 7, so must increase sum by 2, so max at least 2. So answer 2.

    Now consider n=3, k=5: we did M=2. d=5-3=2? Wait n=3,k=5 => r=3, d=2, ceil(2/3)=1, M=2.

    Now consider n=6, k=4: n=6, r=2, d=2, ceil(2/6)=1, M=2. S0=8? Actually ceil(6/4)=2, 2*4=8, D=2, spread among 6 yields max=2? Ceil(D/n)=1, M=2. Check: can we achieve max=1? sum=6 not multiple of 4. Need sum 8, increase by 2; can we keep max=1? No because we need to increase sum to 8, so some numbers must be at least 2. So M=2. But could we achieve max=2? Yes, e.g., two 2's and four 1's sum=8. So answer 2.

    Now what about cases where d >= n? For instance n=2, k=5: d = 5-2=3, ceil(3/2)=2, M=3. S0=5? Actually ceil(2/5)=1, 1*5=5, D=3, spread: we need total 3 extra across 2 numbers. The max becomes 1+ceil(3/2)=1+2=3. So answer 3. Is it achievable? Yes: [3,2] sum=5, max=3. Could we achieve max=2? If both 2 sum=4, not divisible by 5; if [2,1] sum=3; if [2,2] sum=4; if [2,3] sum=5 but max=3. So indeed min max=3.

    So formula holds.

    Thus answer = 1 + ceil( (k - (n % k)) / n ) when n % k != 0; else 1.

    But we can also combine: Let r = n % k; if r == 0: answer=1; else answer = 1 + ceil((k - r) / n). Since (k - r) is positive. Equivalent to answer = ceil( (n + k - 1) / ??? Not exactly.

    Alternative: answer = (n + k - 1) // n? That would be ceil((n)/?) No.

    Let's attempt to find closed form: answer = ceil(ceil(n/k)*k / n). That's straightforward to compute with integer arithmetic: Let t = (n + k - 1) // k (that's ceil(n/k)). Then let numerator = t * k. Then answer = (numerator + n - 1) // n. Because ceil(x / n) = (x + n - 1) // n for integer x, n positive. So answer = ( ( (n + k - 1) // k ) * k + n - 1 ) // n.

    Check: For n=1,k=5: t = (1+5-1)//5 =5//5=1? Actually (1+5-1)=5, //5=1. Then numerator=1*5=5, answer=(5+1-1)//1? Wait n=1, so answer = (5 + 1 - 1)//1 =5//1=5. Works. For n=4,k=3: t=(4+3-1)//3 =6//3=2, numerator=6, answer=(6+4-1)//4 = (9)//4 =2? Actually 9//4=2, but expected 2? Yes, answer=2. For n=8,k=8: t=(8+8-1)//8=15//8=1? Wait 15//8=1 (since integer division floors). Actually (8+8-1)=15, //8=1. numerator=8, answer=(8+8-1)//8=15//8=1, correct. For n=8,k=17: t=(8+17-1)//17=24//17=1, numerator=17, answer=(17+8-1)//8=24//8=3, correct. So formula works.

    Thus for each test case, we compute:

    t = (n + k - 1) // k ans = (t * k + n - 1) // n

    That is O(1) per test case, with 64-bit integers needed because tk could be up to approx (n/k+1)k up to n + k, both up to 2e9, product tk could be up to about 2e9? Actually n,k up to 1e9, t = ceil(n/k) which is at most n (if k=1) then tk = n1 = n, which is up to 1e9. In worst case? Suppose k is large, n=1e9, k=1e9? Then t=1, product=1e9. If n=1e9, k=1, then t=1e9, product=1e9. So product tk is at most max(n, k) maybe up to 1e9? Actually t = ceil(n/k). So t <= n (when k=1) and then tk = n1 = n <= 1e9. When k is larger than n, t=1, tk = k <= 1e9. So product ≤ 1e9? But wait: n and k can both be up to 1e9, but t = ceil(n/k) can be as high as n if k=1, product = n1 = n <= 1e9. If k is something like 500M and n=1e9, then t = ceil(1e9/5e8)=2, product=25e8=1e9. So indeed tk is at most around 2e9? Let's check extremes: n=1e9, k=5e8+1? Then t=ceil(1e9/(5e8+1)) = 2 because 1e9/(5e8+1) ~1.999..., ceil=2, product=2*(5e8+1)=~1e9+2. So up to about 2e9? Actually product could be > 1e9 if k > n? For k=1e9, n=1e9-1? n=999,999,999, k=1,000,000,000 => t = ceil(999,999,999/1e9)=1, product=1e9, ≤1e9. If k is around 1e9 and n is just over half, product might be 2k ≈2e9. But max of k is 1e9, so 2k ≤2e9, which fits within 64-bit integer easily. 2e9 < 2^31 (2.147e9) actually 2e9 is less than 2^31-1=2147483647, so it fits in 32-bit signed int as well. However careful: n=1e9, k=1e9? product = 1e9; but if n=1e9, k=1e9-1? Then t=ceil(1e9/(1e9-1)) = 2 because 1e9/(1e9-1) ≈1.000000001, ceil=2, product=2*(1e9-1)=2e9-2 ~2e9, fits. So product ≤ 2e9, which fits in 32-bit signed. But we also compute (t*k + n - 1) which could be up to ~2e9+1e9=3e9, still within 32-bit signed? 3e9 > 2.147e9, so it might overflow 32-bit signed. For safety, use 64-bit (long long). Since constraints up to 1e9, sum can be up to 3e9, which is < 2^31? Actually 2^31-1 = 2147483647 ~2.147e9, 3e9 > 2.147e9, so exceeds signed 32-bit. However if we use unsigned 32-bit, max is ~4.29e9, which can accommodate 3e9. But to be safe, use 64-bit (long long) in C++.

    Thus solution: For each test case, read n, k, compute:

    t = (n + k - 1) / k (integer division) ans = (t * k + n - 1) / n

    But careful: In languages, integer arithmetic may overflow if we compute t*k as int if 32-bit. So use long long.

    Alternatively, we can derive another formula: ans = 1 + ((k - n%k) + n - 1) // n if n%k !=0 else 1. But that also uses n%k.

    Simplify: Let r = n % k. If r == 0: ans = 1. Else: ans = 1 + ((k - r) + n - 1) // n. But (k - r) could be up to k-1 <= 1e9-1, plus n-1 up to 2e9, okay.

    But both formulas are fine.

    Let's verify with some edge cases.

    Case n=1, k=1: t = (1+1-1)//1 =1//1=1, ans=(1*1+1-1)//1=1//1=1. Good.

    Case n=1, k=2: t = (1+2-1)//2 =2//2=1, ans=(1*2+1-1)//1=2//1=2. Good.

    Case n=2, k=2: t = (2+2-1)//2=3//2=1, ans=(2+2-1)//2=3//2=1? Actually (2+2-1)=3//2=1 but answer should be 1 because we can set both 1, sum=2 divisible by 2. Yes.

    Case n=2, k=3: t=(2+3-1)//3=4//3=1, ans=(3+2-1)//2=4//2=2. Good.

    Case n=3, k=2: t=(3+2-1)//2=4//2=2, ans=(2*2+3-1)//3 = (4+2)//3=6//3=2. Let's test: n=3,k=2. Need sum even. Minimum sum=3, next even >=3 is 4. D=1, spread among 3 gives max=2? Actually ceil(1/3)=1, so max=2. Is that optimal? Array: [2,1,1] sum=4, max=2. Could we get max=1? Sum would be 3 not even. So answer=2. Good.

    Case n=3, k=4: t=(3+4-1)//4=6//4=1, ans=(4+3-1)//3=6//3=2. Check: need sum multiple of 4. Minimal sum=3, next multiple is 4, D=1, max=2. Array [2,1,1] sum=4. Works.

    Case n=4, k=2: t=(4+2-1)//2=5//2=2, ans=(4+4-1)//4? Wait compute: numerator = tk = 22=4, ans=(4+4-1)//4=7//4=1. So answer=1. Indeed n=4 even, can set all ones sum=4 divisible by 2. Good.

    Now consider large values: n=10^9, k=10^9-1. Then r = n % k = 10^9 % (10^9-1) = 1 (since 10^9 = 1*(10^9-1)+1). So d = k - r = (10^9-1) - 1 = 10^9-2. Then ans = 1 + ceil((10^9-2)/10^9) = 1+1=2. So answer=2. Check via formula: t = ceil(n/k) = ceil(10^9/(10^9-1)) = 2, numerator=2*(10^9-1)=2e9-2, ans = (2e9-2 + 10^9 -1)//10^9 = (3e9 -3)//10^9 = 3000000000-3? Actually 3e9 -3 = 2,999,999,997. Dividing by 1e9 gives 2 (since 2*1e9=2e9, remainder 999,999,997). So answer=2. Good.

    Now check if there's any nuance: Could we ever achieve a smaller maximum by not using the minimal total sum? Consider scenario where n is large relative to k such that the minimal multiple of k >= n is far above n? Actually D = (k - r) can be up to k-1. If n is very small, say n=1, then D = k-1. Then M = 1 + ceil((k-1)/1) = k. That's what we get. Could there be a scenario where we could choose a larger sum that results in a smaller max? For n=1, larger sum means larger number, so no. For n>1, could we maybe set some numbers >1 but also some numbers <1? No, numbers must be positive integers, minimum 1. So any sum > S_min would require even larger numbers, leading to larger max. So minimal sum is best.

    Thus the solution is straightforward.

    But wait: There's an alternative perspective: we want the smallest m such that there exists a multiple of k in [n, n*m]. This multiple is S0 = smallest multiple >= n, i.e., ceil(n/k)k. So condition S0 <= nm => m >= ceil(S0/n). So minimal m = ceil(S0/n). So answer is that.

    Hence implement.

    Now constraints: t up to 1000. So O(1) per test.

    Edge Cases: Ensure we use 64-bit for multiplication and addition.

    Now test with provided examples:

    1. 1 5: t=(1+5-1)//5=5//5=1, ans=(1*5+1-1)//1=5//1=5. OK.

    2. 4 3: t=(4+3-1)//3=6//3=2, ans=(2*3+4-1)//4=(6+3)//4=9//4=2. OK.

    3. 8 8: t=(8+8-1)//8=15//8=1, ans=(1*8+8-1)//8=15//8=1. OK.

    4. 8 17: t=(8+17-1)//17=24//17=1, ans=(1*17+8-1)//8=24//8=3. OK.

    Thus correct.

    Now we should consider possibility that n and k are huge up to 10^9, but computations are fine.

    Now write the solution. In C++, we can use:

    #include using namespace std; int main() { int t; cin>>t; while(t--) { long long n, k; cin>>n>>k; long long t = (n + k - 1) / k; long long ans = (t * k + n - 1) / n; cout << ans << endl; } }

    But careful: (n + k - 1) might overflow 32-bit if using int, but we use long long, so fine.

    Alternatively, we can compute using modular arithmetic:

    if (n % k == 0) ans = 1; else { long long d = k - (n % k); ans = 1 + (d + n - 1) / n; }

    Both fine.

    Now, we should ensure that the answer indeed fits within 32-bit? It's at most ceil((ceil(n/k)*k)/n). In worst case, n=1, k=10^9 gives ans=10^9, which fits 32-bit signed? 10^9 < 2^31-1, yes. In other cases, ans is roughly (k/n) +? Actually maximum when n=1 => ans=k up to 1e9. When n is small relative to k, ans could be up to k. So max 1e9, fits in 32-bit signed. But using long long is safe.

    Now we can produce final answer.

    But let's also think about potential pitfalls: The problem says array of n positive integers. They are positive integers, so minimum 1. That's used. So solution stands.

    Thus final solution in Python: For each test case, read n,k; compute t = (n + k - 1)//k; ans = (t*k + n - 1)//n; print(ans).

    All done.

    Now double-check with some random cases using brute force for small n,k to verify.

    Let's brute for n up to maybe 10, k up to 10, compute minimal max via brute search? We can simulate the condition: The minimal m such that there exists a multiple of k in [n, n*m]. So for each m from 1 upward, check if ceil(n/k)k ≤ nm? Actually simpler: compute S0 = smallest multiple of k >= n; then m = ceil(S0/n). So that is the answer. But let's manually test a few:

    n=2,k=4: S0 = 4 (since 2->4), m=ceil(4/2)=2. Could we achieve max=1? sum=2 not divisible by4. So need at least 2. Works.

    n=3,k=2: S0=4, m=ceil(4/3)=2. Works.

    n=3,k=6: S0=6, m=ceil(6/3)=2. Could we have max=1? sum=3 not divisible by6; need sum 6; so at least one number must be 2? Actually to get sum 6 with 3 numbers >=1, we can have [2,2,2] max=2; or [1,1,4] max=4; but min max=2. Yes.

    n=5,k=6: S0=6, m=ceil(6/5)=2. Because 6/5=1.2 ceil=2. So answer 2. Could we have max=1? sum=5 not divisible by6, so need sum 6, must increase sum by 1; so one number becomes 2, max=2.

    n=5,k=8: S0=8, m=ceil(8/5)=2. So answer 2.

    n=5,k=9: S0=9, m=ceil(9/5)=2. Answer 2.

    n=5,k=10: n%k=5, S0=10, m=2? 10/5=2 => 2. Actually n%k=5? k=10, n=5 => r=5, d=5, ceil(5/5)=1, so ans=2. But can we achieve max=1? sum=5 not divisible by10; need sum 10; D=5; spreading 5 among 5 gives each +1, so [2,2,2,2,2] max=2. So yes.

    n=6,k=9: S0=9? 6->9, 9/6=1.5 ceil=2 =>2. D=3, spread gives max=2? ceil(3/6)=1, so max=2. Works.

    Now test a case where n > k. n=10, k=3: n%k=1, d=2, ceil(2/10)=1, ans=2. S0=12? Actually ceil(10/3)=4, 4*3=12, D=2, max=2. Indeed, we can set numbers to sum 12 with max 2? With 10 numbers, sum=12, average 1.2; to keep max 2, we need at least two numbers equal to 2 (since need extra 2). So array: two 2's and eight 1's sum=12, max=2. So answer 2.

    Now test n=10, k=7: n%k=3, d=4, ceil(4/10)=1, ans=2. S0=14, D=4, can have four 2's? Actually need sum=14, extra 4, so four numbers become 2, rest 1, max=2.

    Now test n=10, k=11: n%k=10, d=1, ceil(1/10)=1, ans=2. S0=11, D=1, one number becomes 2, max=2.

    All seems consistent.

    Now consider a case where d >= n, like n=3, k=7: d=4 (since r=3, k-r=4), ceil(4/3)=2, ans=3. S0=7, D=4, spread: we need to add 4 to 3 numbers. The even spread gives max = 1+ ceil(4/3) = 1+2=3. So array could be [2,2,3]? Sum =7? 2+2+3=7, max=3. Or [2,1,4] max=4; [3,2,2] max=3; So min max=3. Works.

    Now consider n=2,k=7: d=5, ceil(5/2)=3, ans=4. S0=7, D=5, max=1+3=4. Can we achieve max=4? Need sum 7 with two numbers <=4: possibilities: (3,4) sum=7, max=4; (4,3) same; (2,5) max=5; so yes. Could we have max=3? Then max ≤3, numbers in {1,2,3}, max sum with 2 numbers is 6, but need sum 7, impossible. So answer 4.

    Now is there any scenario where answer is 0? No, because numbers must be positive integers, min max is at least 1.

    Thus final answer.

    Now we can produce solution.

    But wait, the problem statement: "You should create an array of n positive integers a_1, a_2, ..., a_n such that the sum (a_1 + a_2 + ... + a_n) is divisible by k and maximum element in a is minimum possible." So we need to minimize the maximum element. The answer is the minimal possible maximum.

    We have derived answer = ceil(ceil(n/k)*k / n). Alternatively, we can think of it as: answer = 1 if n % k == 0 else ceil( (n + k - n%k) / n )? Actually S0 = n + (k - n%k) if n%k!=0 else n. So answer = ceil( (n + (k - n%k)) / n ) = ceil(1 + (k - n%k)/n) = 1 + ceil((k - n%k)/n). But note that ceil(1 + x) = 1 + ceil(x) only if x not integer? Actually it's always true: ceil(1+x) = 1 + floor(x)? Wait, let's check: x=1.2, ceil(2.2)=3, 1+ceil(1.2)=1+2=3. x=1.0, ceil(2.0)=2, 1+ceil(1.0)=1+1=2. So it's always true: ceil(1+x) = 1 + ceil(x) because adding 1 shifts the integer part. More formally: ceil(x+1) = ceil(x) + 1. So yes, answer = 1 + ceil((k - n%k)/n). So we can compute that directly.

    Now we need to ensure that the ceil division works for large numbers.

    Also, we can consider using Python's integer arithmetic, which automatically handles big ints.

    Implementation:

    def solve(): import sys input = sys.stdin.readline t = int(input()) out = [] for _ in range(t): n,k = map(int, input().split()) if n % k == 0: out.append('1') else: d = k - (n % k) # ans = 1 + ceil(d / n) ans = 1 + (d + n - 1) // n out.append(str(ans)) print('\n'.join(out))

    But careful: When n%k==0, d =0, then ans = 1 + (0+n-1)//n = 1 + 0 = 1, because (n-1)//n = 0 for n>=1. So we could unify: ans = 1 + ((k - (n%k)) + n - 1)//n. That works even when n%k=0 because (k - 0)+n-1 = k + n -1, but (k + n -1)//n is not necessarily 0; it could be >0, leading to ans>1 incorrectly. Actually when n%k=0, k - (n%k) = k, so 1 + (k + n -1)//n would be >1 unless k <=? Let's test n=4,k=2: n%k=0, then ans = 1 + (2+4-1)//4 = 1 + (5)//4 = 1+1=2, but actual answer is 1. So unify only works if we treat separately or use condition. So better to compute via first method: t = (n + k - 1)//k; ans = (tk + n - 1)//n. That works for all cases because when n%k=0, t = n/k, tk = n, ans = (n + n - 1)//n = (2n -1)//n = 1 for n>=1? Actually (2n-1)//n = 1 if n>=1 because 2n-1 < 2n, floor = 1 for n>1? Let's test n=4: (24-1)//4 =7//4=1, correct. For n=1: (21-1)//1 =1//1=1, correct. So that unified formula works. Good.

    Alternatively, we could compute directly: ans = ( ( (n + k - 1) // k ) * k + n - 1 ) // n. That's the simplest unified.

    Now confirm with n=4,k=2: (4+2-1)//2 =5//2=2, t=2? Actually (4+2-1)=5//2=2, t=2, t*k=4, (4+4-1)//4=7//4=1. Yes ans=1. So that's correct.

    Wait careful: t = (n + k - 1)//k yields ceil(n/k). For n=4,k=2, ceil(4/2)=2 indeed. Then t*k = 4, ans = (4+4-1)//4 = 7//4=1. Good.

    Thus that formula works universally.

    Now one more check: n=1,k=5: (1+5-1)//5=5//5=1, t*k=5, (5+1-1)//1=5//1=5. Good.

    So we can implement in one line.

    Now we should consider the possibility of overflow in Python? Python big ints fine.

    Now the solution seems correct.

    But wait, there might be a nuance: The array elements must be positive integers. In our reasoning, we assumed that we can always achieve any sum between n and nm with numbers between 1 and m inclusive, by incrementing from all 1's. But is that always possible while keeping each element ≤ m? Yes, because we can start from all 1's and increase elements one by one up to m, thus achieving any sum from n to nm. Since each increment increases sum by 1, we can reach any integer. However, we also need the sum to be exactly S0, which is within [n, n*m] for m >= ceil(S0/n). So we can achieve that sum with max ≤ m. So the condition is both necessary and sufficient. So answer is correct.

    Thus final solution.

    We'll produce an explanation and code.

    Now I'll produce final answer. ```python

    import sys

    def solve() -> None: it = iter(sys.stdin.read().strip().split()) t = int(next(it)) out_lines = [] for _ in range(t): n = int(next(it)) k = int(next(it)) # t = ceil(n/k) t = (n + k - 1) // k # ans = ceil(t*k / n) ans = (t * k + n - 1) // n out_lines.append(str(ans)) sys.stdout.write("\n".join(out_lines))

    if name == "main": solve()