题目背景

欢迎新斗友

题目描述

定义一个长度为 $m$ 的非空序列 $p_1,p_2,...,p_m$ 是乱的当且仅当满足以下两个条件。

• 所有元素之和不超过 $n$，即 $\sum_{i=1}^m p_i\le n$。
• 对于任意一个元素 $p_i$ 满足 $p_i=1$ 或 $p_i$ 为质数。

定义一个乱的序列 $p_1,p_2,...,p_m$ 的乱斗值为该序列中所有元素减 $k$ 的平方和，即 $\sum_{i=1}^m (p_i-k)^2$。

特别的，定义一个不乱的序列的乱斗值为 $0$。

现在给定两个正整数 $n,k$，问所有序列中乱斗值最大的序列的乱斗值是多少。

输入格式

本题有多组测试数据。第一行输入一个正整数 $T$，表示测试数据组数，接下来分别输入 $T$ 组数据。

对于每组测试数据，输入一行两个正整数 $n,k$。

输出格式

对于每组测试数据输出一行一个整数表示答案。

5
1 1
2 1
4 1
5 2
10 10

0
1
4
9
810

提示

样例解释

对于样例第 $1,2,3,4$ 组数据，其中一种乱斗值最大的序列分别为 $(1),(2),(1,3),(5)$。

数据范围与约定

对于所有测试点，保证 $1\le T\le 10^3$，$1\le n\le 10^9$，$1\le k\le 5\times 10^4$。