P9817 ******D

Welcome, new “douyou” @[lmxcslD](https://www.luogu.com.cn/user/358957).

Define a non-empty sequence $p_1,p_2,\ldots,p_m$ of length $m$ to be **chaotic** if and only if it satisfies the following two conditions. - The sum of all elements does not exceed $n$, i.e. $\sum_{i=1}^m p_i\le n$. - For every element $p_i$, we have $p_i=1$ or $p_i$ is a prime number. Define the **chaos value** of a **chaotic** sequence $p_1,p_2,\ldots,p_m$ as the sum of squares of each element minus $k$, i.e. $\sum_{i=1}^m (p_i-k)^2$. In particular, define the chaos value of a **non-chaotic** sequence as $0$. Now given two positive integers $n,k$, ask: among all sequences, what is the maximum possible **chaos value**, and output that maximum value.

This problem has multiple test cases. The first line contains a positive integer $T$, the number of test cases. Then $T$ test cases follow. For each test case, input one line with two positive integers $n,k$.

For each test case, output one line with one integer, the answer.

#### Sample Explanation For test cases $1,2,3,4$ in the samples, one possible sequence achieving the maximum **chaos value** is $(1)$, $(2)$, $(1,3)$, $(5)$, respectively. #### Constraints and Notes |Test Point ID|$T$|$n$|$k$|Special Property| |:-:|:-:|:-:|:-:|:-:| |$1$|$=100$|$\le 10$|$\le 10$|None| |$2$|$=200$|$\le 30$|$\le 10$|None| |$3$|$=300$|$\le 10^3$|$\le 5\times 10^4$|None| |$4$|$=400$|$\le 10^5$|$\le 5\times 10^4$|None| |$5$|$=500$|$\le 10^7$|$\le 5\times 10^4$|None| |$6$|$=600$|$\le 10^9$|$=1$|$n$ is prime| |$7$|$=700$|$\le 10^9$|$=1$|None| |$8$|$=800$|$\le 10^9$|$=44444$|None| |$9$|$=900$|$\le 10^9$|$\le 5\times 10^4$|$n$ is prime| |$10$|$=10^3$|$\le 10^9$|$\le 5\times 10^4$|None| For all test points, it is guaranteed that $1\le T\le 10^3$, $1\le n\le 10^9$, and $1\le k\le 5\times 10^4$. Translated by ChatGPT 5