18576번 - Humongous String 다국어

Consider the alphabet Σ = {s₀, . . . , s_k−1} of size k. Define the sequence of strings {T_i} as follows:

• T₀ = s₀;
• T_i = T_i−1s_i mod k for all integers i ≥ 1.

Let S = T₀T₁T₂ . . . be an infinite string which is a concatenation of all strings {T_i} in ascending order of their indices. For example, if k = 3, s₀ = “a”, s₁ = “b”, and s₂ = “c”, then T0 = “a”, T₁ = “ab”, T₂ = “abc”, T₃ = “abca”, T₇ = “abcabcab” (and so on), and S = “aababcabcaabcab. . . ”.

Denote the prefix of string S of length n by S_n. Given numbers n and k, count the number of distinct non-empty substrings of string S_n provided that |Σ| = k.

The first line contains a single integer T (1 ≤ T ≤ 10⁵), the number of test cases.

Then T lines follow. The i-th of these lines contains two integers n_i and k_i (1 ≤ n_i ≤ 10⁹, 1 ≤ k_i ≤ 10⁹) separated by a single space: the length of string S_ni and the size of alphabet Σ in the i-th test case.

Print T lines. The i-th of them should contain a single integer: the answer for the i-th test case.