거대한 문자열

크기가 $k$인 알파벳 $\Sigma = \{s_0, \ldots, s_{k-1}\}$을 생각하자. 다음과 같이 문자열의 수열 $\{T_i\}$를 정의한다.

• $T_0 = s_0$
• 모든 정수 $i \ge 1$에 대해 $T_i = T_{i-1}\, s_{i \bmod k}$

무한 문자열 $S = T_0T_1T_2\ldots$는 모든 $T_i$를 인덱스 오름차순으로 이어 붙인 문자열이다. 예를 들어 $k = 3$이고 $s_0$은 a, $s_1$은 b, $s_2$는 c이면 $T_0$은 a, $T_1$은 ab, $T_2$는 abc, $T_3$은 abca, $T_7$은 abcabcab이다. 이때 $S$는 aababcabcaabcab...이다.

$S$의 길이 $n$인 접두사를 $S_n$으로 표기한다. $n$과 $k$가 주어질 때, $|\Sigma| = k$이고 $S_n$의 서로 다른 비어 있지 않은 부분 문자열의 개수를 구하라.

첫 줄에 테스트 케이스의 개수 $T$ ($1 \le T \le 10^5$)가 주어진다. 이어지는 $T$개의 줄에는 각각 공백으로 구분된 두 정수 $n_i$와 $k_i$ ($1 \le n_i \le 10^9$, $1 \le k_i \le 10^9$)가 주어진다.

$T$개의 줄을 출력한다. $i$번째 줄에는 알파벳 크기가 $k_i$일 때 $S_{n_i}$의 서로 다른 비어 있지 않은 부분 문자열의 개수를 쓴다.