{"raw_statement":[{"iden":"statement","content":"Vilmantas is a real numberphile. He is fascinated by numbers, but most of all he likes numbers, which are named after famous scientist and mathematicians. For example, there are Mersenne primes (MP = 2p - 1, where _p_ is prime), Graham's number (extremely large number, no way to define it here in commonly known notation). \n\nVilmantas would love to have numbers named after him. This is what he came up with. He takes some positive number and extracts every 2-digit number in the given order. For example, if we extract number 10324, we get a sequence of S = {10, 03, 32, 24}. Then he checks for three conditions:\n\nThe previous number 10324 breaks two of the conditions: 3 is prime and while GCD(10, 3) = GCD(3, 32) = 1, 32 and 24 are not coprime (GCD(32, 24) = 8). \n\nIf some number satisfies all three of the conditions, then it is called Vilmantas' number.\n\nGiven numbers a and b, count the Vilmantas' numbers in range [a;b].\n\nThe first line contains the number of test cases _T_ (T ≤ 10). In the following _T_ lines there are integers _a_ and _b_ (1 ≤ a ≤ b ≤ 1011).\n\nFor each test case output one line containing “_Case #tc: num_”, where _tc_ is the number of the test case (starting from 1) and _num_ is the count of Vilmantas' numbers from a to b inclusive.\n\nOnly integers coprime to zero are 1 and  - 1.\n\n"},{"iden":"input","content":"The first line contains the number of test cases _T_ (T ≤ 10). In the following _T_ lines there are integers _a_ and _b_ (1 ≤ a ≤ b ≤ 1011)."},{"iden":"output","content":"For each test case output one line containing “_Case #tc: num_”, where _tc_ is the number of the test case (starting from 1) and _num_ is the count of Vilmantas' numbers from a to b inclusive."},{"iden":"examples","content":"Input41 923 2325 25100 200OutputCase #1: 0Case #2: 0Case #3: 1Case #4: 11"},{"iden":"note","content":"Only integers coprime to zero are 1 and  - 1."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case $ k \\in \\{1, \\dots, T\\} $:  \n- Let $ N_k \\in \\mathbb{Z} $ be the number of dishes.  \n- Let $ A_k = (a_{k,1}, a_{k,2}, \\dots, a_{k,N_k}) $ be a sequence of positive integers representing the calorie values of the dishes.  \n- Let $ M_k \\in \\mathbb{Z} $ be the target total calorie count.  \n- Let $ K_k \\in \\mathbb{Z} $ be the minimum number of distinct perfect recipes required.  \n\n**Constraints**  \n1. $ 1 \\le T \\le 500 $  \n2. For each $ k \\in \\{1, \\dots, T\\} $:  \n   - $ 1 \\le N_k \\le 50 $  \n   - $ 1 \\le a_{k,i} \\le 1000 $ for all $ i \\in \\{1, \\dots, N_k\\} $  \n   - $ 1 \\le M_k \\le 5000 $  \n   - $ 1 \\le K_k \\le 1000 $  \n\n**Objective**  \nFor each test case $ k $, let $ R_k $ be the number of distinct subsets $ S \\subseteq \\{1, \\dots, N_k\\} $ such that:  \n$$\n\\sum_{i \\in S} a_{k,i} = M_k\n$$  \nIf $ R_k \\ge K_k $, output \"ENOUGH\". Otherwise, output $ R_k $.","simple_statement":"Given N dishes, each with Ai calories, find how many different subsets of dishes sum to exactly M calories (each dish used at most once). If there are at least K such subsets, print \"ENOUGH\". Otherwise, print the number of subsets.","has_page_source":false}