Humongous String
시간 제한1초메모리 제한512 MB
각 Ti가 이전 문자열에 순환 문자 하나를 덧붙여 만들어지는 무한 문자열 S = T0T1T2...에서 길이 n인 접두사의 서로 다른 비어 있지 않은 부분 문자열 개수를 구한다.
문제
Consider the alphabet Σ = {s0, . . . , sk−1} of size k. Define the sequence of strings {Ti} as follows:
- T0 = s0;
- Ti = Ti−1si mod k for all integers i ≥ 1.
Let S = T0T1T2 . . . be an infinite string which is a concatenation of all strings {Ti} in ascending order of their indices. For example, if k = 3, s0 = “a”, s1 = “b”, and s2 = “c”, then T0 = “a”, T1 = “ab”, T2 = “abc”, T3 = “abca”, T7 = “abcabcab” (and so on), and S = “aababcabcaabcab. . . ”.
Denote the prefix of string S of length n by Sn. Given numbers n and k, count the number of distinct non-empty substrings of string Sn provided that |Σ| = k.
입력
The first line contains a single integer T (1 ≤ T ≤ 105), the number of test cases.
Then T lines follow. The i-th of these lines contains two integers ni and ki (1 ≤ ni ≤ 109, 1 ≤ ki ≤ 109) separated by a single space: the length of string Sni 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.