有一個雜湊表（hash table）擁有 $m$ 個槽位，編號從 $0$ 到 $m - 1$。初始時，所有槽位皆為空。

有 $n$ 個元素，編號從 $0$ 到 $n - 1$，應依序插入雜湊表中。

雜湊函數為 $h(i) = i^2 \pmod m$，因此編號為 $i$ 的元素將被插入編號為 $(i^2 \pmod m)$ 的槽位中。

由於實作方式較為特殊，將一個元素插入某個槽位的成本為 $T$，其中 $T$ 是該槽位目前已包含的元素數量。請計算將這 $n$ 個元素全部插入表中所需的總成本。

輸入格式

第一行包含一個整數 $t$，代表測試資料的組數 ($1 \le t \le 5$)。

每組測試資料由單一行組成，包含兩個整數 $n$ 和 $m$ ($1 \le n \le 10^9$, $2 \le m \le 10^9$)。

輸出格式

對於每組測試資料，請輸出包含答案的單一行。

範例

輸入 1

3
5 4
1234 5678
5 4

輸出 1

4
229
4

說明

在第一組測試資料中，元素 $0, 1, 2, 3, 4$ 分別被插入槽位 $0, 1, 0, 1, 0$，產生的成本為 $0 + 0 + 1 + 1 + 2 = 4$。