問題一覧 > 通常問題

No.2455 Numbers Dictionary

レベル : / AI推定難易度 : 1500 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 42
作問者 : srjywrdnprkt / テスター : 👑 Nachia
お気に入りにしたユーザー ProblemId : 10024 / 自分の提出
問題文最終更新日: 2023-09-02 00:08:01
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 403 (順位表) の他の問題:

Problem Statement

Taro has a number dictionary that lists the positive integers from $1$ to $N$ in lexicographical order when regarded as strings. Taro wonders at which position in the dictionary the positive integer $K$ appears as an entry. On his behalf, find at which position $K$ appears in lexicographical order.

You are given $T$ test cases. Find the answer for each of them.

Input

$T$
$case_1$
$\vdots$
$case_T$
Here, $case_i$ denotes the $i$-th test case. Each test case is given in the following format.
$N\ K$

All input values are integers and satisfy the following constraints.

  • $1\leq T \leq 10^4$
  • $1\leq K \leq N < 10^{18}$

Output

Output $T$ lines. On the $i$-th line, output the answer to the $i$-th test case.

Sample

Sample 1
Input
3
12 4
999999999999999999 999999999999999999
999999999999999999 100000000000000000
Output
7
999999999999999999
18

For test case number $1$, sorting the integers from $1$ to $12$ in lexicographical order gives $(1, 10, 11, 12, 2, 3, 4,5,6,7,8,9)$. Since $4$ appears at position $7$ from the front, the answer is $7$.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。