In the land of Amestris, alchemists are known for bending matter to their will, shaping stone, fire, and metal in the name of war or progress. But among them stands one who chose a different path — Rutherford, the Nonmetal Alchemist. Unlike others, he turned his back on combat and committed his life to the pursuit of knowledge.
Lately, usage of transmutation across Amestris has grown in intensity, leading to the appearance of never-before-seen elements at an alarming rate! These elements possess unknown properties, and Rutherford believes that their electron configurations, more specifically, the number of electrons in the final shell of their atoms, hold the key to understanding them.
Every element in the universe is made of atoms, and each atom in its neutral state has a specific number of electrons equal to its atomic number $$$Z$$$. These electrons orbit the nucleus, and each electron is uniquely described by four integers called quantum numbers.
The number of electrons that can fill in a subshell $$$(n, \ell)$$$ is determined by the number of valid $$$(n, \ell, m, s)$$$ combinations (each representing an electron). For example, if $$$S = 2$$$, the subshell $$$(2, 1)$$$ has a capacity of $$$6$$$ electrons. The quantum numbers for those $$$6$$$ electrons are $$$(2, 1, -1, 1)$$$, $$$(2, 1, -1, 2)$$$, $$$(2, 1, 0, 1)$$$, $$$(2, 1, 0, 2)$$$, $$$(2, 1, 1, 1)$$$, $$$(2, 1, 1, 2)$$$.
For any atom, electrons fill subshells in increasing order of energy, following the Aufbau principle. The energy of a subshell is primarily determined by $$$n + \ell$$$, and in case of ties, the subshell with the smaller $$$n$$$ is filled first. According to this rule, the first $$$10$$$ subshells filled are: $$$(1, 0)$$$, $$$(2, 0)$$$, $$$(2, 1)$$$, $$$(3, 0)$$$, $$$(3, 1)$$$, $$$(4, 0)$$$, $$$(3, 2)$$$, $$$(4, 1)$$$, $$$(5, 0)$$$, $$$(4, 2)$$$. The final shell of an atom is the largest value of $$$n$$$ that has a non-zero number of electrons.
For $$$S = 2$$$, the electrons of Germanium, an atom with atomic number $$$32$$$, enter the subshells in the following order:
The electron configuration of Germanium can be written in shorthand as $$$(1, 0)^2 (2, 0)^2 (2, 1)^6 (3, 0)^2 (3, 1)^6 (3, 2)^{10} (4, 0)^2 (4, 1)^2$$$, where $$$(n, \ell)^k$$$ means that $$$k$$$ electrons are placed in the subshell $$$(n, \ell)$$$. So, the final shell for this atom is shell $$$4$$$, and the number of electrons on the final shell is $$$2 + 2 = 4$$$.
You are Bohr, Rutherford's student — curious, determined, and eager to assist your mentor in his mission. Help Rutherford calculate the number of electrons in the final shell for any atom, given its atomic number $$$Z$$$ and $$$S$$$, the number of possible spin values for electrons in this universe.
The first line contains a single integer $$$t \: (1 \leq t \leq 10^5)$$$ — the number of test cases.
The first line of each test case contains two space-separated integers $$$q \: (1 \leq q \leq 10^5)$$$ and $$$S \: (1 \leq S \leq 10^5)$$$ — the number of atoms and the number of possible spin values for electrons in this universe.
The second line of each test case contains $$$q$$$ space-separated integers $$$Z_1, Z_2, \dots, Z_q \: (1 \leq Z_i \leq 10^{12})$$$ — where $$$Z_i$$$ is the atomic number of the $$$i$$$-th atom.
It is guaranteed that the sum of $$$q$$$ over all test cases doesn't exceed $$$10^6$$$.
For each test case, output $$$q$$$ space-separated integers in a line — the $$$i$$$-th of which should be the number of electrons in the final shell for the $$$i$$$-th given atom in the given universe.
Output tokens may be separated by arbitrary whitespace (spaces, tabs, or newlines). Trailing whitespace at the end of lines or at the end of the output will not affect the verdict.
41 23210 29 10 11 12 17 18 19 20 35 361 7352 21 1000000000000
47 8 1 2 7 8 1 2 7 8281 2
The first test case is explained in the statement.
In the third case, the electron configuration is $$$(1, 0)^7 (2, 0)^7 (2, 1)^{21}$$$. So, in a universe with $$$7$$$ electron spins, Bromine is a noble gas.
| Название |
|---|


