{"problem":{"name":"Digit vs Square Root","description":{"content":"Solve the following problem for $T$ test cases. Given an integer $N$, find the number of integers $x$ that satisfy all of the following conditions: *   $1 \\le x \\le N$ *   Let $y = \\lfloor \\sqrt{x} \\","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc174_d"},"statements":[{"statement_type":"Markdown","content":"Solve the following problem for $T$ test cases.\nGiven an integer $N$, find the number of integers $x$ that satisfy all of the following conditions:\n\n*   $1 \\le x \\le N$\n*   Let $y = \\lfloor \\sqrt{x} \\rfloor$. When $x$ and $y$ are written in decimal notation (without leading zeros), $y$ is a prefix of $x$.\n\n## Constraints\n\n*   $T$ is an integer such that $1 \\le T \\le 10^5$.\n*   $N$ is an integer such that $1 \\le N \\le 10^{18}$.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$T$\n$N_1$\n$N_2$\n$\\vdots$\n$N_T$\n\nHere, $N_i$ represents the integer $N$ for the $i$\\-th test case.\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc174_d","tags":[],"sample_group":[["2\n1\n174","1\n22\n\nThis input contains two test cases.\n\n*   For the first test case, $x=1$ satisfies the conditions since $y = \\lfloor \\sqrt{1} \\rfloor = 1$.\n*   For the second test case, for example, $x=100$ satisfies the conditions since $y = \\lfloor \\sqrt{100} \\rfloor = 10$."]],"created_at":"2026-03-03 11:01:14"}}