Background

Welcome, new “douyou”

Problem Description

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.

Input Format

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$.

Output Format

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

5
1 1
2 1
4 1
5 2
10 10

0
1
4
9
810

Hint

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

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