AT_arc224_d.Angst for All Pairs

There are $N$ cards, numbered $1$ through $N$. Initially, nothing is written on any of the cards.

You can write zero or more positive integers on each card.

The cost of writing a positive integer $k$ once is equal to the number of digits in the decimal representation of $k$.

Determine whether it is possible to satisfy the following condition. If it is possible, output the minimum total cost required; if it is not possible, output $-1$.

• For every pair of positive integers $(x,y)$ satisfying $1 \leq x < y \leq K$, there exists a card containing exactly one of $x$ and $y$.

$T$ test cases are given; solve each of them.

有 $N$ 张卡片，编号为 $1$ 至 $N$。初始时，所有卡片上均未写入任何数字。

你可以在每张卡片上写零个或多个正整数。

每次写入一个正整数 $k$ 的代价等于 $k$ 的十进制表示的位数。

请判断是否可能满足以下条件。若可能，输出所需的最小总代价；否则输出 $-1$：

• 对于每一对满足 $1 \leq x < y \leq K$ 的正整数 $(x, y)$，都存在一张卡片，其上恰好包含 $x$ 和 $y$ 中的一个（即 $x$ 和 $y$ 中恰有一个出现在该卡片上）。

共给出 $T$ 组测试用例，请对每组分别求解。

The input is given from Standard Input in the following format, where $\mathrm{case}_i$ denotes the $i$-th test case:

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

Each test case is given in the following format:

$N$ $K$

输入从标准输入给出，格式如下，其中 $\mathrm{case}_i$ 表示第 $i$ 个测试用例：

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

每个测试用例的格式如下：

$N$ $K$

Output $T$ lines. The $i$-th line should contain the answer for the $i$-th test case.

输出 $T$ 行。第 $i$ 行应包含第 $i$ 个测试用例的答案。

Sample 1 Explanation:
This input contains four test cases.

For the first test case, writing as follows satisfies the condition with a total cost of $5$.

• Write $1, 5$ on card $1$.
• Write $2, 5$ on card $2$.
• Write $3$ on card $3$.

For the second test case, the minimum total cost required to satisfy the condition is $39$.

For the third test case, it is impossible to satisfy the condition, so output $-1$.

For the fourth test case, the minimum total cost required to satisfy the condition is $17655598$.

Constraints

• $1 \leq T \leq 10^5$
• $1 \leq N \leq 10^6$
• $2 \leq K \leq 10^6$
• The sum of $N$ in each input is at most $10^6$.
• The sum of $K$ in each input is at most $10^6$.
• All input values are integers.

样例 1 解释：
该输入包含四个测试用例。

对于第一个测试用例，按如下方式书写可满足条件，总代价为 $5$：

• 在卡片 $1$ 上写 $1, 5$；
• 在卡片 $2$ 上写 $2, 5$；
• 在卡片 $3$ 上写 $3$。

对于第二个测试用例，满足条件所需的最小总代价为 $39$。

对于第三个测试用例，无法满足条件，因此输出 $-1$。

对于第四个测试用例，满足条件所需的最小总代价为 $17655598$。

约束条件

• $1 \leq T \leq 10^5$
• $1 \leq N \leq 10^6$
• $2 \leq K \leq 10^6$
• 所有输入中 $N$ 的总和不超过 $10^6$。
• 所有输入中 $K$ 的总和不超过 $10^6$。
• 所有输入值均为整数。