{"raw_statement":[{"iden":"statement","content":"Hey, it's your friend Crazy Rich Sean! You haven't seen him since the last time you visited Singapore. It turns out he's even crazier and even richer than before. People think that the sign of being rich is being able to afford private jets with caviar and Iberico ham and solid gold toilet seats. The true craziest and richest of society can afford to buy _ideas_—democracy, truth, and most importantly, _numbers_.\n\nCrazy Rich Sean bought a shiny new integer sequence. Don't even bother looking for it in the OEIS, since Crazy Rich Sean's team of lawyers has copyrighted, patented, and trademarked this sequence for his exclusive use.\n\nDefine the sequence $R$ as the unique nondecreasing sequence of positive integers $R (1), R (2), R (3), \\\\dots$ such that for every $i >= 1$, $i$ appears in the sequence exactly $R (i) + R (i + 1)$ times. It starts as: $$\\begin{array}{r|rrrrrrrrrrrrrrrrrrrr} i & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & \\dots \\\\ \\hline R(i) & 1 & 1 & 2 & 2 & 2 & 3 & 3 & 3 & 3 & 4 & 4 & 4 & 4 & 5 & 5 & 5 & 5 & 5 & 6 & \\dots \\end{array}$$\n\nCrazy Rich Sean wants to test out this new integer sequence by playing a game with his employees. Each of his employees has a unique ID number which is some positive integer, and he has an employee for every positive integer. For this game, he announces that all employees whose ID number is between $a$ and $b$ (inclusive) must participate. The participating employees must line up in one long queue. An employee with ID number $x$ is considered _safe_ if (and only if) at least one of the following is true:\n\nAll employees that are not safe will end up fired. That's awful! Why would Sean do this? Because he's crazy, and rich, and he'll get away with it too, thanks to that aforementioned team of lawyers. \n\nDue to your friendship, Crazy Rich Sean allows one concession—you are allowed to decide the order in which the employees should line up. Among all possible queueing orders, what is the minimum number of employees that will end up fired?\n\nThe first line of input contains $t$, the number of test cases. The following $t$ lines describe the test cases. \n\nEach test case consists of a single line containing two space-separated integers $a$ and $b$. \n\nFor each test case, output a single integer denoting the answer for that test case. \n\n*For all subtasks*\n\n$1 <= t <= 4 dot.op 10^5$\n\n$1 <= a <= b <= 2 dot.op 10^(18)$\n\n*Subtask 1* (7 points): $b <= 10$, $t <= 30$\n\n*Subtask 2* (7 points): $b <= 20$, $t <= 30$\n\n*Subtask 3* (6 points): $b <= 30$\n\n*Subtask 4* (7 points): $b <= 100$\n\n*Subtask 5* (8 points): $b <= 3000$, $t <= 500$\n\n*Subtask 6* (20 points): $b <= 2 dot.op 10^5$, $t <= 500$\n\n*Subtask 7* (5 points): $b <= 10^6$\n\n*Subtask 8* (5 points): $b <= 2^(32)$, $t <= 500$\n\n*Subtask 9* (5 points): $b <= 2^(32)$\n\n*Subtask 10* (5 points): $b <= 10^(12)$, $t <= 500$\n\n*Subtask 11* (5 points): $b <= 10^(12)$\n\n*Subtask 12* (5 points): $b <= 10^(15)$, $t <= 500$\n\n*Subtask 13* (5 points): $b <= 10^(15)$\n\n*Subtask 14* (5 points): $t <= 500$\n\n*Subtask 15* (5 points): No additional constraints.\n\nHere's one possible queueing order of employees $1$ to $10$ (from back to front): $$7, 4, 10, 1, 5, 2, 9, 3, 6, 8$$\n\nWith this queueing order, you can verify that $6$ employees will end up getting fired. The only safe employees are employees $1$, $2$, $4$ and $8$. \n\nIt can also be shown that any other queueing order will have $6$ or more employees end up getting fired. Therefore, the answer for the first sample case is $6$. \n\n"},{"iden":"input","content":"The first line of input contains $t$, the number of test cases. The following $t$ lines describe the test cases. Each test case consists of a single line containing two space-separated integers $a$ and $b$. "},{"iden":"output","content":"For each test case, output a single integer denoting the answer for that test case. "},{"iden":"scoring","content":"*For all subtasks*$1 <= t <= 4 dot.op 10^5$$1 <= a <= b <= 2 dot.op 10^(18)$*Subtask 1* (7 points): $b <= 10$, $t <= 30$*Subtask 2* (7 points): $b <= 20$, $t <= 30$*Subtask 3* (6 points): $b <= 30$*Subtask 4* (7 points): $b <= 100$*Subtask 5* (8 points): $b <= 3000$, $t <= 500$*Subtask 6* (20 points): $b <= 2 dot.op 10^5$, $t <= 500$*Subtask 7* (5 points): $b <= 10^6$*Subtask 8* (5 points): $b <= 2^(32)$, $t <= 500$*Subtask 9* (5 points): $b <= 2^(32)$*Subtask 10* (5 points): $b <= 10^(12)$, $t <= 500$*Subtask 11* (5 points): $b <= 10^(12)$*Subtask 12* (5 points): $b <= 10^(15)$, $t <= 500$*Subtask 13* (5 points): $b <= 10^(15)$*Subtask 14* (5 points): $t <= 500$*Subtask 15* (5 points): No additional constraints."},{"iden":"note","content":"Here's one possible queueing order of employees $1$ to $10$ (from back to front): $$7, 4, 10, 1, 5, 2, 9, 3, 6, 8$$With this queueing order, you can verify that $6$ employees will end up getting fired. The only safe employees are employees $1$, $2$, $4$ and $8$. It can also be shown that any other queueing order will have $6$ or more employees end up getting fired. Therefore, the answer for the first sample case is $6$. "}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, q \\in \\mathbb{Z}^+ $.  \nLet $ \\mathbf{p} = (p_1, p_2, \\dots, p_n) $ where $ p_i \\in \\{1, \\dots, n\\} $, defining a functional graph on $ n $ nodes.  \nFor each query:  \n- Let $ r_1, r_2 \\in \\mathbb{Z} $ with $ 0 \\le r_1 \\le r_2 \\le 10^9 $.  \n- Let $ d \\in \\mathbb{Z}^+ $, and $ S = \\{s_1, s_2, \\dots, s_d\\} \\subseteq \\{1, \\dots, n\\} $, with all $ s_i $ distinct.  \n\n**Constraints**  \n1. $ 1 \\le t \\le 10 $  \n2. $ \\sum_{\\text{test cases}} n \\le 250000 $, $ \\sum_{\\text{test cases}} q \\le 250000 $, $ \\sum_{\\text{test cases}} d \\le 250000 $  \n3. For all $ i \\in \\{1, \\dots, n\\} $, $ 1 \\le p_i \\le n $  \n4. For each query, $ s_i \\in \\{1, \\dots, n\\} $, distinct  \n\n**Objective**  \nFor each query, find the set $ X \\subseteq \\{1, \\dots, n\\} $ of all possible starting departments such that, after applying $ \\mathbf{p} $ repeatedly, the paperwork passes through **at least one** node in $ S $ at some step $ k $ satisfying $ r_1 \\le k \\le r_2 $.  \n\nCompute:  \n$$\n\\sum_{x \\in X} x^2\n$$","simple_statement":"You are given a directed graph with n nodes, where each node i points to p_i.  \nFor each query, you are given:  \n- A range [r1, r2]  \n- A set of d distinct departments s1, s2, ..., sd  \n\nYou must find all possible starting departments such that, after following the redirects (p_i), you reach one of the s_i departments after exactly k steps, where k is in [r1, r2].  \n\nOutput the sum of the squares of all such possible starting departments.","has_page_source":false}