Problem Description

Author: eedwang

我總是想讓我和百鬼あやめ的互動充滿樂趣和驚喜。今晚，我們在一起玩一個小謎題遊戲。為了考驗我們的默契，あやめ提出了一些關於密碼的條件，這些條件取決於兩個變數 k 和 x。

每一個密碼都是一個長度為 n 的字串 s，必須滿足以下性質：

1. 字串 s 只能使用英文字母表中的前 k 個小寫字母。
2. 對於字串中任意兩個位置的索引 i 和 j (1≤i<j≤n)，如果它們的距離 (j−i) 能被 x 整除，那麼這兩個位置上的字母 si 和 sj 必須不同。

我的任務是找出最小的整數 n，使得在這個長度下，不存在任何符合上述條件的有效字串（即無論怎麼填都會違反規則）。

Input Format

第一行包含一個整數 t (1≤t≤500)，表示測試資料的組數。 每組測試資料包含一行兩個整數 k 和 x (1≤k≤26,1≤x≤15)。

Output Format

對於每組測試資料，輸出最小的 n。

3
2 1
3 2
1 5

3
7
6