Skip to content
TheChatArchiveThe Chat Archive
DeepSeekDeepseek v3.2· deepseekHugging Face Frontier Reasoning Traces

SKIT’s canteen sells Patties in packages of 6, 9 or 20 . Thus, it is possible, for…

  1. User

    SKIT’s canteen sells Patties in packages of 6, 9 or 20 . Thus, it is possible, for example, to buy exactly 15 Patties (with one package of 6 and a second package of 9), but it is not possible to buy exactly 16 Patties, since no non- negative integer combination of 6's, 9's and 20's add up to 16. To determine if it is possible to buy exactly n Patties, one has to find non-negative integer values of a, b, and c such that

    6a+9b+20c=n

    Being an Engineer you are given task to find out whether an order is packable or not. Input:

    First line of the input contains an integer T, denoting the number of test cases, only to be followed by T lines each containing the order units U.

    Output:

    Output contains T lines, each having either True or False depending upon if the order is packable.

    Constraints:

    1 ≤ T ≤ 50 1 ≤ U ≤ 10^7

    SAMPLE INPUT 2 45 1

    SAMPLE OUTPUT True False

    Explanation

    As evident that no package is available for 1 unit but for 45 units ,it can be packaged in 5 : 9 unit packs or 6 : 6 unit packs and 1 : 9 unit pack

  2. DeepSeek Assistant

    We need to determine for each U (order units) whether there exist non-negative integers a, b, c such that 6a+9b+20c = U.

    Given constraints: U up to 10^7, T up to 50. Brute force with loops could be okay if we use efficient method.

    Observation: Since 6 and 9 share gcd 3, and 20 mod 3 = 2, overall equation solvable if U mod gcd(6,9,20) is 0? gcd(6,9,20)=1? gcd(6,9)=3, gcd(3,20)=1, so overall gcd=1. So for sufficiently large U, all numbers should be representable? Not necessarily: Coin problem: Frobenius number for three numbers may exist. But since gcd=1, there exists a largest integer not representable. We need to find that number or test each U efficiently.

    We could precompute representable up to some bound. But U up to 10^7, T 50, we could test each U by exploring possibilities. But naive triple loop would be too slow.

    We can treat it as a linear Diophantine equation. Since 6 and 9 have gcd 3, we can reduce: Let U be given. Write 6a+9b = 3k where k = 2a+3b, so basically 3k + 20c = U. So we need integers k>=0 (where k = 2a+3b, and a,b >=0). But any integer k that can be expressed as 2a+3b with a,b>=0? Let's analyze: 2a+3b can represent all integers >=? Actually, using coin problem with 2 and 3: gcd(2,3)=1, so all integers >= (23 - 2 - 3)=1? Actually Frobenius number for 2 and 3 is 1, meaning every integer >= 2 can be expressed as nonnegative combination of 2 and 3? But note we need a,b >=0. 0 = 02+03; 1 cannot be expressed; 2 =12; 3=13; 4=22; 5=12+13; 6=32 or 23; etc. So indeed all integers except 1 can be expressed as 2a+3b. But we also have constraint that a,b nonnegative. So the set S = {2a+3b: a,b>=0} = all integers >=0 except 1. Let's verify: 0 works (a=b=0); 1 no; 2 yes; 3 yes; 4 yes; 5 yes; 6 yes; etc. So S = {0,2,3,4,5,6,...}. Actually also 7? 7=22+13; yes. So all integers except 1. So k can be any nonnegative integer not equal to 1. So equation reduces to existence of nonnegative integers k (≠1? but we can also consider that if k=1, there is no representation with a,b>=0, but maybe we could get directly from 6a+9b? Actually 6a+9b = 3(2a+3b). So any multiple of 3 can be obtained by appropriate a,b? Not exactly: 6a+9b yields multiples of 3 obviously. But the condition from (a,b) is that (U-20c) must be divisible by 3 and the quotient, say k = (U-20c)/3, must be representable as 2a+3b with a,b>=0. Since S includes all integers except 1, the condition is: there exists c>=0 such that U-20c >=0, divisible by 3, and (U-20c)/3 is not equal to 1. Also if (U-20c)/3 = 0, that's fine (a=b=0). If it's negative? U-20c>=0.

    So we can test for each c from 0 to floor(U/20). For each c, compute remainder = U - 20c. If remainder % 3 == 0, then let k = remainder/3. If k != 1, then it's possible. Also need to consider k=0? That's okay: corresponds to a=b=0, only c packages. So condition: k != 1. Also ensure that k>=0 obviously.

    But is that the only condition? Check: Does every k != 1 have a,b>=0? Yes, as argued. But what about k=0? Yes. So we can say if there exists c such that (U-20c) is non-negative, divisible by 3, and (U-20c)/3 != 1, then representable.

    But is there any other nuance? Let's test some numbers: U=1, c=0 => remainder 1, not divisible by 3; c can't be >0. So false.

    U=2, c=0: remainder 2, not divisible by 3; false? But 2 cannot be expressed with 6,9,20? 2 is less than 6,9,20 so false. So correct.

    U=3, c=0: remainder 3, divisible by 3 => k=1 -> k=1 not allowed => false. Indeed 3 cannot be expressed (since smallest package is 6). So false.

    U=4? false.

    U=5? false.

    U=6: c=0 => remainder 6 %3=0, k=2 !=1 -> true. 6=6a with a=1.

    U=7? 7%? c=0 => 7%3=1; c cannot be >0 because 20>7. So false.

    U=8? c=0 remainder 8%3=2 false; false.

    U=9: c=0 remainder 9%3=0, k=3 !=1 -> true (9=1*9).

    U=10? c=0 remainder10%3=1 false. c? 20c>10 only c=0, false.

    U=11? similarly false.

    U=12: remainder12%3=0, k=4 !=1 -> true (2*6).

    U=13? false.

    U=14? false.

    U=15: remainder15%3=0, k=5 !=1 -> true (6+9).

    U=16? remainder16%3=1 false. So false.

    U=17? false? 17%3=2, so false.

    U=18: remainder18%3=0, k=6 !=1 -> true (36 or 29).

    U=19? false.

    U=20: c=0 remainder20%3=2? Actually 20%3=2, not divisible. But c=1 => remainder=0, divisible, k=0 !=1 -> true (c=1). So 20 works. Also maybe other combos.

    U=21: c=0 remainder21%3=0, k=7 !=1 -> true (6+15? but 15 not directly, but 21=6+15? 15 not a single package but combination: 6+15 cannot since 15=6+9, so overall 6+6+9=21). So true.

    U=22: c=0 remainder22%3=1 false; c=1 remainder2 not divisible; so false? Can we do 22? 6+? 16 no; 9+?13 no; 20+?2 no. So false.

    U=23: c=0 remainder23%3=2 false; c=1 remainder3%3=0, k=1? Wait 23-20=3, remainder=3, k=1, which is not allowed -> false. So 23 false.

    U=24: c=0 remainder24%3=0, k=8 !=1 -> true (4*6). Also c=1 remainder4%3=1 false. So true.

    U=25: c=0 remainder25%3=1 false; c=1 remainder5%3=2 false. So false? 25 cannot? 6+?19 no; 9+?16 no; 20+?5 no; 6+9+?10 no. So false.

    U=26: c=0 remainder26%3=2 false; c=1 remainder6%3=0, k=2 !=1 -> true (20+6). So 26 true.

    U=27: c=0 remainder27%3=0, k=9 -> true (3*9). Also c=1 remainder7%3=1 false. So true.

    U=28: c=0 remainder28%3=1 false; c=1 remainder8%3=2 false; false? 28? Could it be 8? Actually 28=6+?22 no; 9+?19 no; 20+8 no; 6+6+?16 no; 6+9+?13 no; 9+9+?10 no; 6+6+6+?10 no; 6+9+9+?4 no; 20+6+?2 no. So false. Indeed.

    U=29: c=0 remainder29%3=2 false; c=1 remainder9%3=0, k=3 !=1 -> true (20+9). So true.

    U=30: c=0 remainder30%3=0, k=10 !=1 -> true (5*6). Also c=1 remainder10%3=1 false. So true.

    U=31: c=0 remainder31%3=1 false; c=1 remainder11%3=2 false; false? 31? Maybe 6+9+?16 no; 6+6+?19 no; 9+9+?13 no; 20+?11 no; 6+6+6+?13 no; 6+9+9+?7 no; 20+6+?5 no; 20+9+?2 no; 6+6+9+?10 no; 6+6+6+6+?7 no. So false.

    U=32: c=0 remainder32%3=2 false; c=1 remainder12%3=0, k=4 !=1 -> true (20+12 -> 20+6+6). So true.

    U=33: c=0 remainder33%3=0, k=11 !=1 -> true (311? but 33=311, but 11 not directly, but combination: 6+9+?18? Actually 33=6+9+?18=6+9+6+6+? not clear. But we know from condition: k=11 can be represented as 2a+3b? 11 = 24+31 (a=4,b=1 gives 64+91=24+9=33). So true.

    U=34: c=0 remainder34%3=1 false; c=1 remainder14%3=2 false; false? 34? 20+14? 14 not possible; 6+28? 28 not; 9+25? 25 not; 6+6+22? 22 not; 9+9+16? 16 not; 20+6+8? 8 not; 20+9+5?5 not; 6+6+6+16?16 not; 6+6+9+13?13 not; 6+9+9+10?10 not; 9+9+9+7?7 not; 6+6+6+6+10?10 not; 20+6+6+2?2 not; So false. So condition holds.

    U=35: c=0 remainder35%3=2 false; c=1 remainder15%3=0, k=5 !=1 -> true (20+15, 15=6+9). So true.

    U=36: c=0 remainder36%3=0, k=12 !=1 -> true (6*6). So true.

    U=37: c=0 remainder37%3=1 false; c=1 remainder17%3=2 false; false? 37? 20+17? 17 not; 6+31?31 not; 9+28?28 not; 6+6+25?25 not; 6+9+22?22 not; 9+9+19?19 not; 20+6+11?11 not; 20+9+8?8 not; 6+6+6+19?19 not; 6+6+9+16?16 not; 6+9+9+13?13 not; 9+9+9+10?10 not; 20+6+6+5?5 not; 20+6+9+2?2 not; 6+6+6+6+13?13 not; So false.

    U=38: c=0 remainder38%3=2 false; c=1 remainder18%3=0, k=6 !=1 -> true (20+18, 18=36 or 29). So true.

    U=39: c=0 remainder39%3=0, k=13 !=1 -> true (e.g., 6*? Actually 13=25+31 gives 6*5+9=30+9=39). So true.

    U=40: c=0 remainder40%3=1 false; c=1 remainder20%3=2 false; c=2 remainder0%3=0, k=0 -> true (2*20). So 40 true.

    U=41: c=0 remainder41%3=2 false; c=1 remainder21%3=0, k=7 !=1 -> true (20+21,21=6+15 but we know 21 true). So true.

    U=42: c=0 remainder42%3=0, k=14 !=1 -> true (6*7 or combos). So true.

    U=43: c=0 remainder43%3=1 false; c=1 remainder23%3=2 false; c=2 remainder3%3=0, k=1 -> not allowed, so false? Let's test manually: 43. 20+?23 ->23 false. 40+?3 ->3 false. 6*? 67=42, remainder1 false. 9? 94=36, remainder7 false; 95=45 too big. 6+9+?28?28 false. 6+6+9+?22 false. 6+6+6+9+?16 false. 9+9+9+?16 false. 20+6+?17 false. 20+9+?14? 14 false. 20+6+6+?11 false. 20+6+9+?8 false. 20+9+9+?5 false. 6+6+6+6+?19 false. 6+6+6+9+?16 false. 6+6+9+9+?13 false. 6+9+9+9+?10 false. 9+9+9+9+?7 false. 6+6+6+6+6+?9? That is 30+?13 false. 6+6+6+6+9+?10 false. 20+20+?3 false. So likely false. Condition yields false.

    U=44: c=0 remainder44%3=2 false; c=1 remainder24%3=0, k=8 !=1 -> true (20+24,24=4*6). So true.

    U=45: true as sample.

    Seems condition works.

    But we need to be careful: The mapping from k to (a,b) is: given k = 2a+3b, we need to find nonnegative a,b. For k != 1, it's always possible. But what about k=0? Yes. So condition is simply: exists c>=0 such that (U-20c) >=0, (U-20c)%3==0, and (U-20c)/3 != 1. However, is there any case where (U-20c)/3 = 1 but still there is a representation? That would correspond to U-20c = 3, which means U = 20c + 3. If we can represent 3 using 6a+9b? 3 cannot be represented by 6 and 9 because they are multiples of 3 but the smallest positive is 6. So 3 itself cannot be represented. But could there be representation using different c? If U = 20c + 3 and we try to use another c' such that (U-20c') is divisible by 3 and k !=1, then representation exists. So condition covers that.

    Now, we must also consider that the mapping from k to (a,b) is not one-to-one but existence is guaranteed for k != 1. Let's double-check boundary: k=0? gives 0, a=b=0 works. k=2? a=1,b=0 works. k=3? a=0,b=1 works. k=4? a=2,b=0 works. k=5? a=1,b=1 works. k=6? a=3,b=0 or a=0,b=2. So yes.

    Thus algorithm: For each U, iterate c from 0 while 20c <= U. Compute rem = U - 20c. If rem % 3 == 0: let k = rem / 3; if k != 1: return True. After loop, return False.

    Complexity: For each U up to 10^7, maximum c is floor(10^7/20) = 500,000. That's 500k iterations per test case. With T up to 50, total up to 25 million iterations, which is fine in Python (since each iteration is simple arithmetic). However, 500k * 50 = 25M, definitely okay within time limit (usually 1-2 seconds maybe borderline but likely fine). But we can optimize further.

    We can also solve using modular arithmetic. Since 20 mod 3 = 2, we can treat U mod 3 conditions.

    Let's analyze more systematically: Condition exists if ∃ c>=0 s.t. U - 20c ≡ 0 (mod 3) and (U-20c)/3 ≠ 1. Since 20c mod 3 = (20 mod 3)*c = 2c mod 3. So condition U ≡ 2c (mod 3). For each U mod 3, we can find c mod 3 that works.

    Case 1: U ≡ 0 mod 3. Then we need 2c ≡ 0 mod 3 => c ≡ 0 mod 3 (since 2 invertible mod3, inverse of 2 is 2 because 22=4≡1 mod3). So c = 3t. Then rem = U - 20(3t) = U - 60t. k = rem/3 = U/3 - 20t. We need k != 1. So essentially we need to check if there exists t such that U/3 - 20t >= 0 and U/3 - 20t != 1. Since t can be 0,1,2,... floor(U/60). For t=0, k = U/3. If U/3 != 1 => U != 3, then we have representation if U/3 >= 0 obviously. So for U ≡ 0 mod 3 and U != 3, t=0 works unless U/3 = 1 i.e., U=3, but that's excluded. So for all U ≡ 0 mod 3, except U=3, representation exists? Check U=0? U>=1, so ignore. U=6 works, U=9 works, U=12 works, U=15 works, U=18 works, U=21 works, U=24 works, U=27 works, U=30 works, U=33 works, U=36 works, U=39 works, U=42 works, U=45 works, U=48? 48 mod3=0, U=48, k=16, works. But what about U=0? Not needed. But what about U=3? fails. U=3 is false. So for all multiples of 3 except 3, true? Let's test U=0 (not needed). U=3 false. But is there any other multiple of 3 that might fail? Consider U = 3? Already false. But maybe U = something like 3 + 20c? But that would be U=23,43,63,... but those are not multiples of 3. 23 mod3=2, 43 mod3=1, 63 mod3=0? 63=3+60, so U=63. According to rule, since 63 ≡ 0 mod3, and 63 !=3, t=0 gives k=21, which !=1, so true. But check if 63 is representable: 63 = 3*21; we need to represent 63 as 6a+9b+20c. With t=0 (c=0), we need 6a+9b=63 => divide by 3: 2a+3b=21, which is representable because 21 !=1, so yes (a=9,b=1 gives 54+9=63). So true. So indeed all multiples of 3 except 3 are representable.

    But wait: What about U=6? true, U=9 true, U=12 true. So condition seems fine.

    But we must also consider the case when k becomes negative? Not with t=0, k positive.

    Case 2: U ≡ 1 mod 3. Then we need 2c ≡ 1 mod 3 => c ≡ 2 mod 3 (since 2*2=4≡1). So c = 2 + 3t. Then rem = U - 20(2+3t) = U - 40 - 60t. For this to be non-negative, we need U >= 40 + 60t. The smallest c is 2. So we need U >= 40 (since t=0 gives c=2). For t=0: rem = U - 40; k = (U-40)/3. Condition: k != 1 and k >=0. So if U >=40 and (U-40)/3 != 1 => U != 43. So for U ≡1 mod3 and U>=40 and U≠43, representation exists? Let's test. Examples: U=40? Actually 40 mod3 = 1 (since 39 is multiple, 40 mod3=1). Then c=2 => rem=0, k=0 => true. So 40 works. U=43: we saw false. U=46: 46 mod3=1? 45 multiple, 46≡1. c=2 => rem=6, k=2 => true (46=40+6). So 46 true. U=49: 49-40=9, k=3 => true. U=52: 52-40=12, k=4 => true. U=55: 55-40=15, k=5 => true. U=58: 58-40=18, k=6 => true. U=61: 61-40=21, k=7 => true. U=64: 64-40=24, k=8 => true. U=67: 67-40=27, k=9 => true. U=70: 70-40=30, k=10 => true. etc. So for U>=40 and U≠43, appears true.

    But what about U=1,4,7,10,13,16,19,22,25,28,31,34,37? These are <40 and ≡1 mod3. They all false as per earlier tests? Let's check: 1 false, 4 false, 7 false, 10 false, 13 false, 16 false, 19 false, 22 false, 25 false, 28 false, 31 false, 34 false, 37 false. So for U<40 and ≡1 mod3, false. So for U ≡1 mod3, condition is U>=40 and U≠43? Actually 43 is the only potential exception? Could there be another? Let's test U=43 false; U=46 true; U=49 true; What about U= 40+60t? That's U=100? 100 mod3? 99 multiple, 100≡1. c=2+3t? For t=1, c=5: rem=100-100=0, k=0 true. So fine. But what about U= 43+60t? For t=0, U=43 false. For t=1, U=103? 103 mod3= 102+1 ≡1. Then c could be 2? Let's check: For U=103, try c=2: rem=103-40=63, k=21 true. So actually 103 is representable. But according to our pattern: if we use c=2, then k=21 !=1, so it works. Wait but 43 false because k=1. For U=103, with c=2, k=21, true. So only when (U-40)/3 = 1, i.e., U=43, is problematic. But could there be cases where the smallest c (c=2) yields k negative? For U<40, c=2 not allowed because rem negative. So we need to check larger c values? For U ≡1 mod3, we need c ≡2 mod3. Could there be a case where the smallest c such that rem>=0 yields k=1? That would be when U -20c = 3, i.e., U = 20c+3. Since U ≡1 mod3, 20c+3 ≡ 2c+0 ≡2c mod3. For this to be ≡1 mod3, 2c ≡1 => c ≡2 mod3. So indeed if U = 20c+3 with c ≡2 mod3, then rem=3, k=1 -> not allowed. So for any c = 2 mod3, if U = 20c+3, it's a candidate for failure. That is U = 20*(3t+2)+3 = 60t+40+3 = 60t+43. So U = 43,103,163,223,...? Wait 60t+43, for t=0:43, t=1:103? But 103 we found works because there is also c=5? Actually 103 = 60*1+43. For t=1, c=5? Let's check: c=5 yields rem = 103 -100 = 3, k=1 -> not allowed. But we also have c=2: rem=63, k=21 allowed. So failure only if the only c that gives divisible by 3 yields k=1, but if there is another c that also gives divisible by 3 and k !=1, then it's okay. So we must consider all possible c, not just the smallest with the required modulo class. So the condition we need to check is existence of any c. So for U ≡1 mod3, we should examine all c ≡2 mod3 such that rem>=0. There could be multiple such c. So we can't just check the smallest; we need to see if any yields k !=1.

    Therefore, the simple iteration over c from 0 to floor(U/20) is straightforward and safe. However, we might optimize by noticing that for sufficiently large U, all numbers are representable. The Frobenius number for three numbers? Since gcd=1, there is a largest non-representable number. We could compute that number and then for U larger than that, always return True. But with U up to 10^7, we can just iterate c (max 500k) which is okay. 500k per test case may be acceptable in Python if T=50? 25 million loops, each a few operations, should be within 2-3 seconds maybe borderline but likely okay for typical competitive programming constraints with time limit 1-2 sec? 25 million loops in Python could be around 0.5-1 sec if simple? Actually Python can handle ~50 million simple operations per second on fast machines? Not exactly, typical CP Python can handle ~50 million operations maybe 2 seconds. But 25 million loops with modulo and division may be okay. But we can further reduce loop: Since we only need to check c mod 3 specific values, we can reduce iterations by factor 3. For each U, we can compute the remainder class needed. Let's do that.

    We need to find any c in [0, floor(U/20)] such that (U - 20c) % 3 == 0 and (U - 20c)/3 != 1. The condition (U-20c) % 3 == 0 gives a congruence on c: 20c ≡ U (mod 3) → 2c ≡ U (mod 3). So c ≡ (2^{-1} * U) mod 3. Since 2 inverse mod3 is 2 (since 22=4≡1), c ≡ 2U mod 3? Actually: 2c ≡ U mod 3 => multiply both sides by 2: 4c ≡ 2U mod3 → c ≡ 2U mod3 (since 4≡1). So c ≡ 2U (mod 3). So c must be congruent to r = (2U) % 3. Since mod3 yields 0,1,2. So for each U, we only need to test c values that are congruent to r modulo 3. That reduces number of c to about floor(U/20)/3 ≈ 166k per test case (max). 166k * 50 = 8.3 million, even better.

    But we also need to check condition k != 1. However, for most c, k will be large. But we must still check.

    Alternatively, we could compute the Frobenius number for set {6,9,20}? But easier is to just iterate.

    Given constraints: T ≤ 50, U ≤ 10^7. The worst-case U=10^7, floor(10^7/20)=500,000. Doing 500k iterations for 50 test cases = 25 million. That's okay in Python with efficient code. Even if time limit is strict, we can micro-optimize: use a while loop, avoid function calls, use local variables, etc. But we can also precompute for all U up to some bound? Up to 10^7 is too large to precompute an array of booleans of size 10^7+1? 10 million booleans is okay in Python? A list of booleans of length 10^7 would be about 80 MB (since each bool is an object? Actually using Python list of bools, each entry is a Python object (True/False) taking ~28 bytes each, so 10 million * 28 = 280 MB, too large. Using bytearray or bitset: bytearray of 10 million is 10 MB, which is acceptable. But we need to compute representability for all numbers up to 10^7? That could be done with DP? Since we have three numbers, we could use a boolean DP like coin change, but that would be O(N) per number? Actually we could compute using a sieve: for each package size, mark multiples. But combination sums require DP. We could do something like: generate all numbers representable by 6,9,20 up to 10^7 using a boolean array; start with dp[0]=True; for each coin, for i from coin to U_max: dp[i] = dp[i] or dp[i-coin]. That's O(U_max * number_of_coins) = 3*10^7 = 30 million operations, which is fine, and then answering queries in O(1). However, we must also consider that dp array size 10^7+1 as a bytearray is 10 MB, plus the DP loop, 30 million operations in Python might be okay if optimized using list of bools? Actually Python loops over 10 million would be heavy. We could use bit operations? But simple DP with list of booleans and for loops might be slower than per test iteration. But we could also use a mathematical characterization.

    Given the pattern we derived, we can solve each U in O(1) with some case analysis. Let's attempt to derive a closed form.

    We have: ∃ c≥0 such that (U-20c) ≡ 0 (mod 3) and (U-20c)/3 ≠ 1. Let r = U mod 3. Then c ≡ 2U mod 3 (as derived). So there exists a c if we can pick c in the set S = {c0, c0+3, c0+6, ...} where c0 = r * 2? Actually compute r = U%3, then 2U mod3 = (2*(U%3))%3 = (2r)%3. So c0 = (2r) % 3? But that yields a residue class, not a specific starting value. However, the smallest non-negative c with that residue is c_min = (2r) % 3? Actually if r=0: c ≡ 0 mod3 => smallest c = 0. r=1: c ≡ 2 mod3 => smallest c = 2. r=2: c ≡ 1 mod3 => smallest c = 1. So we can define:

    • If U%3 == 0: try c = 0,3,6,... up to <=U/20.
    • If U%3 == 1: try c = 2,5,8,... (i.e., start from 2, step 3).
    • If U%3 == 2: try c = 1,4,7,... (start from 1, step 3).

    Now we need to check if any such c yields k = (U-20c)/3 that is not equal to 1 and also obviously k >=0 (which is guaranteed if c <= U/20). So the condition reduces to existence of an integer t >= 0 such that c = c0 + 3t <= floor(U/20) and (U-20c)/3 != 1.

    Note that (U-20c)/3 is decreasing as c increases. For smallest c (c_min), k is largest. For larger c, k decreases. We need to find any c in the arithmetic progression that yields k != 1. Since only one value of k could be 1 (if it appears in the progression), we can check if the smallest c gives k >=0 and (if the smallest c gives k != 1, then true). If the smallest c gives k=1, then we may check the next c in the progression (c+3). But careful: If the smallest c yields k=1, that means U - 20c = 3 => U = 20c+3. Since c is minimal satisfying the residue, we have c = c_min (the smallest possible). Then we can try c = c_min+3, which gives U - 20(c_min+3) = (U - 20c_min) - 60 = 3 - 60 = -57, which is negative if U -20c_min is only 3 and 3-60 negative, but that only applies if c_min+3 <= floor(U/20)? In this case, if U = 20c_min+3, then floor(U/20) = c_min (since 20c_min+3 // 20 = c_min). So c_min+3 exceeds floor(U/20). So there is no next c. So if the only valid c yields k=1, then false. But could there be a case where the smallest c yields k negative? No because c_min is chosen as the smallest non-negative satisfying residue. c_min is at most 2, so for U small, c_min might be > floor(U/20) meaning no c at all? Actually we must ensure c_min <= floor(U/20) for there to be any c. So if c_min > floor(U/20), then there is no c satisfying the congruence and non-negativity condition, so false. But could there be a scenario where c_min yields k negative? If c_min > U/20 then we wouldn't consider it because rem negative. So we need to check if there exists any c in progression <= floor(U/20). If none, false. If there is at least one, we need to see if any yields k != 1. Since k decreases as c increases, and there could be multiple c values. But note that if the smallest c (i.e., the largest k) yields k >=0 but k could be 1, then maybe a larger c yields k >=0 and not 1? However, as we increase c, k becomes smaller. If the smallest c yields k=1, that implies U-20c_min=3. For the next c = c_min+3, we have U-20(c_min+3) = U-20c_min-60 = 3-60 = -57, which is negative, so not allowed. So there is no larger c because c_min+3 > floor(U/20) given that U = 20c_min+3, so floor(U/20)=c_min. So indeed if the smallest c yields k=1, there are no other c values. So the only potential false cases are when the smallest (and only) valid c yields k=1. But what about when there are multiple c values and the smallest yields k>1, then it's true. But could there be case where the smallest valid c yields k < 0? That would mean c_min > floor(U/20), so no valid c. So false. Or if c_min yields k=0? That's fine. So the condition essentially: Check if there exists any c in the progression such that c <= floor(U/20). If yes, then let k = (U-20c)/3 for the smallest such c (since that gives k largest). If that k != 1, then true. If that k == 1, then false (since no other c). But is it always the case that if the smallest c yields k=1, there is no other c? We need to confirm that for any U, if the smallest c (c_min) in the progression that satisfies c_min <= floor(U/20) yields k=1, then the next c (c_min+3) would exceed floor(U/20). Indeed because if U-20c_min = 3, then U = 20c_min+3. Then floor(U/20) = c_min. So c_min+3 > c_min => no more. So that's fine.

    But what if the smallest c yields k > 1 but the next c yields k = 1? Could that happen? That would require (U-20(c_min+3))/3 = 1 => U-20c_min-60 = 3 => U-20c_min = 63 => but then from smallest c we have k = (U-20c_min)/3 = 21, which is not 1, so representation exists already via smallest c. So true. So only need to check the smallest valid c.

    But wait: Could there be a situation where there is no c_min because c_min > floor(U/20) but there is a larger c that satisfies the residue? For example, U=20? Let's test: U=20, U%3=2. Then c ≡ 2*2 mod3 = 4 mod3 =1. Smallest c =1. floor(20/20)=1, so c=1 is valid. So smallest exists. For U=10, U%3=1, c ≡2 mod3, smallest c=2, floor(10/20)=0, so c_min=2 > 0 => no valid c. Could there be c=5? 5>0 but floor(10/20)=0, so any c>=1 is > floor, so no valid c. So indeed if smallest c (which is the smallest non-negative integer with that residue) is > floor(U/20), then no c exists because all other c are larger. So checking smallest c suffices.

    Thus we can determine representability by:

    • Compute r = U % 3.
    • Determine c0 based on r: if r == 0: c0 = 0 if r == 1: c0 = 2 if r == 2: c0 = 1
    • If c0 > U // 20: return False.
    • Compute k = (U - 20*c0) // 3. (Since we know it's divisible because of congruence)
    • If k == 1: return False.
    • Else: return True.

    But is that always correct? Let's test with various numbers.

    Test U=0? Not needed. U=3: r=0, c0=0, c0 <= floor(3/20)=0? 0 <= 0 true. k = (3-0)/3 =1 => false. Correct.

    U=6: r=0, c0=0, k=2 => true. Good.

    U=9: r=0, c0=0, k=3 => true.

    U=12: k=4 => true.

    U=15: k=5 => true.

    U=18: k=6 => true.

    U=20: r=2, c0=1, check c0 <= floor(20/20)=1 yes, k=(20-20)/3=0 => true.

    U=21: r=0, c0=0, k=7 => true.

    U=22: r=1, c0=2, floor(22/20)=1 => c0=2 >1 => false. Good.

    U=23: r=2, c0=1, floor(23/20)=1, k=(23-20)/3=1 => false. Good.

    U=24: r=0, c0=0, k=8 => true.

    U=25: r=1, c0=2 > floor(25/20)=1 => false.

    U=26: r=2, c0=1 <= floor(26/20)=1, k=(26-20)/3=2 => true.

    U=27: r=0, k=9 => true.

    U=28: r=1, c0=2 > floor(28/20)=1 => false.

    U=29: r=2, c0=1 <= floor(29/20)=1, k=(29-20)/3=3 => true.

    U=30: r=0, k=10 => true.

    U=31: r=1, c0=2 > floor(31/20)=1 => false.

    U=32: r=2, c0=1 <= floor(32/20)=1, k=4 => true.

    U=33: r=0, k=11 => true.

    U=34: r=1, c0=2 > floor(34/20)=1 => false.

    U=35: r=2, c0=1 <= floor(35/20)=1, k=5 => true.

    U=36: r=0, k=12 => true.

    U=37: r=1, c0=2 > floor(37/20)=1 => false.

    U=38: r=2, c0=1 <= floor(38/20)=1, k=6 => true.

    U=39: r=0, k=13 => true.

    U=40: r=1, c0=2 <= floor(40/20)=2? floor=2. c0=2 <=2, k=(40-40)/3=0 => true.

    U=41: r=2, c0=1 <= floor(41/20)=2, k=(41-20)/3=7? Actually 41-20=21, /3=7 => true. Also could check c0=1, yes.

    U=42: r=0, c0=0, k=14 => true.

    U=43: r=1, c0=2 <= floor(43/20)=2, k=(43-40)/3=1 => false. Good.

    U=44: r=2, c0=1 <= floor(44/20)=2, k=(44-20)/3=8 => true.

    U=45: r=0, k=15 => true.

    U=46: r=1, c0=2 <= floor(46/20)=2, k=2 => true.

    U=47: r=2, c0=1 <= floor(47/20)=2, k=(47-20)/3=9 => true? Wait 47-20=27/3=9, yes true. Check if 47 is representable? 20+27=47, and 27 is representable (3*9), so yes.

    U=48: r=0, k=16 => true.

    U=49: r=1, c0=2 <= floor(49/20)=2, k=3 => true.

    U=50: r=2, c0=1 <= floor(50/20)=2, k=(50-20)/3=10 => true? 20+30=50, 30=5*6, yes.

    U=51: r=0, k=17 => true.

    U=52: r=1, c0=2 <= floor(52/20)=2, k=4 => true.

    U=53: r=2, c0=1 <= floor(53/20)=2, k=(53-20)/3=11 => true.

    U=54: r=0, k=18 => true.

    U=55: r=1, c0=2 <= floor(55/20)=2, k=5 => true.

    U=56: r=2, c0=1 <= floor(56/20)=2, k=12 => true? Actually 56-20=36/3=12, yes.

    U=57: r=0, k=19 => true.

    U=58: r=1, c0=2 <= floor(58/20)=2, k=6 => true.

    U=59: r=2, c0=1 <= floor(59/20)=2, k=(59-20)/3=13 => true? 20+39=59, 39 representable, yes.

    U=60: r=0, k=20 => true.

    U=61: r=1, c0=2 <= floor(61/20)=3? Actually floor(61/20)=3, since 20*3=60. So c0=2 <=3, k=(61-40)/3=7? Wait careful: using c0=2: (61-40)=21/3=7 => true. So fine.

    U=62: r=2, c0=1 <=3, k=(62-20)/3=14 => true.

    U=63: r=0, k=21 => true.

    U=64: r=1, c0=2 <=3, k=(64-40)/3=8 => true.

    U=65: r=2, c0=1 <=3, k=(65-20)/3=15 => true.

    U=66: r=0, k=22 => true.

    U=67: r=1, c0=2 <=3, k=9 => true.

    U=68: r=2, c0=1 <=3, k=16 => true.

    U=69: r=0, k=23 => true.

    U=70: r=1, c0=2 <=3 (floor=3), k=10 => true.

    U=71: r=2, c0=1 <=3, k=17 => true.

    U=72: r=0, k=24 => true.

    U=73: r=1, c0=2 <=3, k=11 => true.

    U=74: r=2, c0=1 <=3, k=18 => true.

    U=75: r=0, k=25 => true.

    U=76: r=1, c0=2 <=3 (floor=3), k=12 => true.

    U=77: r=2, c0=1 <=3, k=19 => true.

    U=78: r=0, k=26 => true.

    U=79: r=1, c0=2 <=3, k=13 => true.

    U=80: r=2, c0=1 <=4? floor(80/20)=4, so c0=1 <=4, k=(80-20)/3=20 => true. Also c0=1 works.

    U=81: r=0, k=27 => true.

    U=82: r=1, c0=2 <=4, k=(82-40)/3=14 => true.

    U=83: r=2, c0=1 <=4, k=(83-20)/3=21 => true.

    U=84: r=0, k=28 => true.

    U=85: r=1, c0=2 <=4, k=(85-40)/3=15 => true.

    U=86: r=2, c0=1 <=4, k=(86-20)/3=22 => true.

    U=87: r=0, k=29 => true.

    U=88: r=1, c0=2 <=4, k=16 => true.

    U=89: r=2, c0=1 <=4, k=23 => true.

    U=90: r=0, k=30 => true.

    U=91: r=1, c0=2 <=4, k=17 => true.

    U=92: r=2, c0=1 <=4, k=24 => true.

    U=93: r=0, k=31 => true.

    U=94: r=1, c0=2 <=4, k=18 => true.

    U=95: r=2, c0=1 <=4, k=25 => true.

    U=96: r=0, k=32 => true.

    U=97: r=1, c0=2 <=4, k=19 => true.

    U=98: r=2, c0=1 <=4, k=26 => true.

    U=99: r=0, k=33 => true.

    U=100: r=1, c0=2 <=5, k=20 => true.

    Now check some border cases: U=43 we already did. U=103? Let's test formula: U=103, r=1 (since 102 multiple), c0=2 <= floor(103/20)=5, k=(103-40)/3=21 => true. So formula says true. Good.

    What about U=23? r=2, c0=1 <= floor(23/20)=1, k=1 => false. So it's fine.

    What about U=3? r=0, c0=0, k=1 => false.

    U=0? Not in input.

    What about U= 20? true.

    What about U= 40? true.

    Now consider U= 6? true.

    Thus it seems the condition is simply: if c0 <= U//20 and k != 1.

    But we must also consider possibility that k could be negative? But if c0 <= U//20, then U-20c0 >= 0. So k >=0.

    So we have an O(1) solution per test case.

    But wait, is it always sufficient to only consider the smallest c in the progression? Let's examine a case where c0 > U//20, so no c. But could there be a larger c that satisfies residue and is <= U//20? For instance, if U=20, r=2, c0=1, U//20=1, so c0=1 works. For U=40, r=1, c0=2, U//20=2, works. For U=60, r=0, c0=0 works. For U=80, r=2, c0=1 works. For U=100, r=1, c0=2 works. For U=110? 110//20=5, r=110%3= (108+2) => r=2, c0=1 <=5 works. So the smallest c is always within 0,1,2. So if U//20 is less than c0 (which is either 0,1,2), then no c exists because any valid c must be at least c0. And since c0 is small (0,1,2), if U//20 < c0, that means U < 20*c0? Actually if c0=1, then U//20 <1 => U <20. So U from 0 to 19. For those U, we need to see if any representation exists with c>=1? But c0=1 is the smallest c with correct residue. If U<20, then the only possible c is 0. But c=0 may or may not have the correct residue. So if c0=1 and U<20, there is no c=0 in the progression because c=0 does not satisfy the residue? For r=2, c must be ≡1 mod3, so c=0 is not allowed. So indeed there is no c. But is it possible that representation exists with c=0 even if c0=1? For r=2, the condition (U-20c) %3 ==0 with c=0 gives U%3==0. So if U%3==0, then c=0 is allowed. But if r=2, that means U%3=2, so c=0 gives remainder 2, not 0. So no. So indeed no representation. So our condition holds.

    Thus the algorithm is:

    For each U: if U < 0? (not) compute r = U % 3 if r == 0: c = 0 elif r == 1: c = 2 else: # r == 2 c = 1 if c > U // 20: output False else: k = (U - 20*c) // 3 if k == 1: output False else: output True

    But we must also consider the case where U is exactly 0? Not needed.

    Now, double-check with some larger numbers and also some edge conditions like U=2? r=2 => c=1, but U//20=0, c>0 => false. Good.

    U=5? r=2 => c=1 >0 => false.

    U=8? r=2 => c=1 >0? 8//20=0 => false.

    U=11? r=2 => c=1 >0 false.

    U=14? r=2 => false.

    U=17? r=2 => false.

    U=20? r=2 => c=1 <=1, k=0 => true.

    U=23? r=2 => c=1 <=1, k=1 => false.

    U=26? r=2 => c=1 <=1, k=2 => true.

    U=29? true.

    U=32? true.

    U=35? true.

    U=38? true.

    U=41? true.

    U=44? true.

    U=47? true.

    U=50? true.

    U=53? true.

    U=56? true.

    U=59? true.

    U=62? true.

    U=65? true.

    U=68? true.

    U=71? true.

    U=74? true.

    U=77? true.

    U=80? true.

    U=83? true.

    U=86? true.

    U=89? true.

    U=92? true.

    U=95? true.

    U=98? true.

    U=101? 101%3=2 => c=1 <= floor(101/20)=5, k=(101-20)/3=27 => true.

    U=104? 104%3=2 => c=1 <=5, k=28 => true.

    U=107? 107%3=2 => c=1 <=5, k=29 => true.

    U=110? 110%3=2 => c=1 <=5, k=30 => true.

    Seems fine.

    Now check numbers with r=1, U<40? Already false.

    U=40: true, 43 false, 46 true, 49 true, 52 true, 55 true, 58 true, 61 true, 64 true, 67 true, 70 true, 73 true, 76 true, 79 true, 82 true, 85 true, 88 true, 91 true, 94 true, 97 true, 100 true.

    Now check U=43, we have false. U=103? r=1, c=2 <=5, k=21 true.

    U=163? r=163%3= (162+1) =>1, c=2 <= floor(163/20)=8, k=(163-40)/3=41 => true. So only numbers of the form 60t+43? Actually 43, 103? Wait 103 gave true because c=2 gives k=21, but we also have c=5 gives k=1? Let's test: For U=103, c=5: 103-100=3 => k=1, but c=5 is also valid? Check: c must be ≡2 mod3, 5 mod3=2, yes. And c=5 <= floor(103/20)=5. So there are two c values: c=2 and c=5. For c=2, k=21 (true). For c=5, k=1 (false). Since at least one gives true, overall true. In our simplified check, we only consider the smallest c (c=2) and it gives true, so we output true. So correct.

    Now what about U= 20*2+3 = 43? For U=43, the residue class r=1 yields c0=2. c0=2 <= floor(43/20)=2. Next c would be 5, but 5 >2, so only c=2. So only k=1, false. So 43 is false.

    Now what about U= 205+3 = 103? Smallest c is 2 (since c0=2) and that yields k !=1, so true. So only numbers of the form 60t+43? Actually 43 corresponds to t=0? 43 = 202+3 where c_min=2, but also it's 600+43. 103 = 601+43, but we have c0=2 works. So the only false ones in r=1 are those where the smallest c (which is 2) yields k=1, which requires U = 202 + 3 = 43. But could there be other false numbers in r=1 where c0=2 > floor(U/20)? That would be U < 40, and those are false. So essentially false for U=1,4,7,10,13,16,19,22,25,28,31,34,37, and also U=43? Actually U=40 is true, so false for U=1,4,7,10,13,16,19,22,25,28,31,34,37, and also U=43? Wait check 40 true, 43 false, 46 true. So 43 is extra false among >=40. Are there any others like 103? 103 true. So only 43 is the sole false in r=1 for U>=40? But what about U= 208+3 = 163? That is 163, we have c0=2 gives k=(163-40)/3=41, true. So only 43.

    Now for r=2: false for U=2,5,8,11,14,17, and also U=23? Actually U=20 true, 23 false, 26 true, 29 true, 32 true, 35 true, 38 true, 41 true, 44 true, 47 true, 50 true, ... So false for U=2,5,8,11,14,17,23? Also check U=23 is false, U= 201+3? 23 = 201+3. Here c0=1 (since r=2), and floor(23/20)=1, so c0=1 yields k=1, false. So 23 is false. Are there other false for U>=20? Possibly U= 204+3 = 83? But 83 we saw true because c0=1 gives k=21? Wait 83: U=83, r=2, c0=1, k=(83-20)/3=21, true. So only when U = 20c0 + 3, with c0 being the smallest c (1 for r=2, 2 for r=1, 0 for r=0 but r=0 gives c0=0 and U=3 yields false). So we have false when U = 3 (r=0), U = 23 (r=2, c0=1), U = 43 (r=1, c0=2). Also any U < 20 where c0 > floor(U/20) yields false. Those are many. Also check U=0? not needed.

    But wait: Could there be false for r=0 where c0=0 but k=1? That's U=3 only. But what about U=0? not considered. So the only false for U>=40 (?) Actually 43 is false and 23 is false but 23<40. For U>=44, all true? Let's test some borderline: U=44 true, 45 true, 46 true, 47 true, 48 true, 49 true, 50 true. U=51 true, 52 true, 53 true, 54 true, 55 true, 56 true, 57 true, 58 true, 59 true, 60 true. So it seems all numbers >= 44 are representable? But check U=61 true, 62 true, 63 true, 64 true, 65 true, 66 true, 67 true, 68 true, 69 true, 70 true, 71 true, 72 true, 73 true, 74 true, 75 true, 76 true, 77 true, 78 true, 79 true, 80 true, 81 true, 82 true, 83 true, 84 true, 85 true, 86 true, 87 true, 88 true, 89 true, 90 true, 91 true, 92 true, 93 true, 94 true, 95 true, 96 true, 97 true, 98 true, 99 true, 100 true. So indeed it seems beyond 43, all numbers are representable. But what about 44,45,..., we've seen all true. Could there be any false beyond 43? Let's test 44 to 50 we did. 51 to 60 all true. So seems the Frobenius number for set {6,9,20} might be 43. Indeed, known result: for McNugget numbers with 6,9,20, the largest non-McNugget number is 43? Wait typical McNugget problem uses 6,9,20 and the largest non-representable is 43. Yes, that's a known fact: with packs of 6, 9, and 20 McNuggets, the largest number that cannot be ordered is 43. So indeed for any U >= 44, it's representable. So we can simply check: if U >= 44, output True. But we must also consider U=0? not needed. However, this known result holds for non-negative integer combinations. But we need to double-check: Is 44 representable? Yes 20+46=44. 45 is 59 or 56+? Actually 45=59, or 36+39? 36+39=18+27=45. So yes. 46=20+26+? Actually 20+26=32? No 20+26=32, need 14; better 20+? 26? 20+26=46, 26=20+6? That would be 220+6=46. Yes 220+6=46. 47=20+27? 27=39, so 20+39=47. 48=86, 49=... 49=20+29? 29 not but 49= 220+9=49? 40+9=49. Yes. 50=20+30 (30=56) or 2*20+10? not but 20+30 works. So indeed all from 44 onward are representable. So we can output True for any U >= 44. For U < 44, we need to check manually.

    But is 43 the largest non-representable? I recall that 43 is indeed the largest for 6,9,20. Let's verify all numbers from 1 to 43 representability:

    List non-representable: 1,2,3,4,5,7,8,10,11,13,14,16,17,19,20? 20 is representable (20 pack). So 20 true. 22? 22 not; 23 not; 25? 25 not; 26 true; 28? 28 not; 29 true; 31 not; 32 true; 34 not; 35 true; 37 not; 38 true; 40 true; 41 true; 43 not. So the non-representable numbers up to 43: 1,2,3,4,5,7,8,10,11,13,14,16,17,19,22,23,25,28,31,34,37,43? Wait also 20 is true, 21 true, 24 true, 26 true, 27 true, 29 true, 30 true, 32 true, 33 true, 35 true, 36 true, 38 true, 39 true, 40 true, 41 true, 42 true, 43 false. Did we miss 44? true. So indeed 43 is largest.

    But note 20 is representable, 21 true, 22 false, 23 false, 24 true, 25 false, 26 true, 27 true, 28 false, 29 true, 30 true, 31 false, 32 true, 33 true, 34 false, 35 true, 36 true, 37 false, 38 true, 39 true, 40 true, 41 true, 42 true, 43 false. So non-representable set: {1,2,3,4,5,7,8,10,11,13,14,16,17,19,22,23,25,28,31,34,37,43}. That's 22 numbers.

    Thus we can simply precompute a set of non-representable numbers up to 43 and for U >=44 return True. That is trivial.

    But the problem constraints U up to 10^7, so this is easy.

    Thus solution: read T, for each U: if U in set_of_false return False else True. But careful: The set includes numbers like 20? Wait 20 is true, so not in set. So only those false ones. So we can check:

    if U >= 44: print("True") else: print("True" if U in representable_set else "False") where representable_set is all numbers from 0..43 that are representable. But easier: just compute with the earlier O(1) formula which works for all U. But given the simplicity, we can implement the O(1) logic, as it's robust and avoids precomputation.

    But I must double-check: Is it indeed true that all U >= 44 are representable? Let's confirm with known Frobenius number for {6,9,20}. I recall that for coprime (gcd=1) sets, the Frobenius number exists but may be large. For {6,9,20}, gcd=1, and the Frobenius number is 43 indeed. But we should verify with some random larger numbers: 44 we did; 45; 46; 47; 48; 49; 50; 51; 52; 53; 54; 55; 56; 57; 58; 59; 60; 61; 62; 63; 64; 65; 66; 67; 68; 69; 70; 71; 72; 73; 74; 75; 76; 77; 78; 79; 80; 81; 82; 83; 84; 85; 86; 87; 88; 89; 90; 91; 92; 93; 94; 95; 96; 97; 98; 99; 100; all seem representable. Also 101, 102, 103 etc. So yes.

    Thus we can implement:

    if U >= 44: print("True") else: representable = set of all true numbers less than 44. Or just compute using simple condition.

    But to be absolutely safe, we could also incorporate the O(1) formula which will also return true for U>=44.

    But the simplest is to just use the known Frobenius number: Since maximum U is 10^7, we can just output True for U >=44, else check.

    However, the problem might expect the general solution, but either is fine.

    I'll adopt the O(1) formula because it's mathematically derived and doesn't rely on known result. But also we can include early exit if U>=44. But we need to be careful: the derivation assumed that the smallest c in the progression is the only one that matters. But we should double-check some edge case: U=0? not input. U=1..43 we can compute manually. But what about U=44? According to formula: r=44%3=2, c0=1, floor(44/20)=2, so c0=1 <=2, k=(44-20)/3=8, not 1 => True. Good. So formula gives True for all U>=44? Let's test U=44,45,... we did. So it's consistent.

    Thus the algorithm:

    For each test case: U = int(input().strip()) r = U % 3 if r == 0: c = 0 elif r == 1: c = 2 else: # r == 2 c = 1 if c > U // 20: print("False") else: k = (U - 20*c) // 3 if k == 1: print("False") else: print("True")

    But wait: For U=0? Not needed.

    But check U=20: r=2, c=1, U//20=1, k=0, not 1 => True.

    U=40: r=1, c=2, U//20=2, k=0 => True.

    U=60: r=0, c=0, k=20 => True.

    U=80: r=2, c=1, U//20=4, k=20 => True.

    U=100: r=1, c=2, U//20=5, k=20 => True.

    U= 10000000: let's compute: U%3? 10^7 % 3 = 1? 9,999,999 is divisible by 3? 9,999,999 /3 = 3,333,333, so 10,000,000 - 9,999,999 = 1 => r=1, c=2, U//20 = 500,000, so c<=, k = (10^7 - 40)/3 = (9,999,960)/3 = 3,333,320, which is not 1 => True. So works.

    Thus algorithm O(1) per test case.

    But wait: The derivation that c must satisfy c ≡ 2U mod 3, and the smallest c is as defined. However, we assumed that if the smallest c yields k >=0 and k !=1, then it's representable. But is it possible that the smallest c yields k that is not representable even though k !=1? Because we need to ensure that k can be expressed as 2a+3b. Our earlier reasoning claimed that any integer except 1 can be expressed as 2a+3b. But is that truly all nonnegative integers except 1? Let's verify again: The set of numbers representable as 2a+3b with a,b >=0. Since gcd(2,3)=1, the Frobenius number for 2 and 3 is 1 (2*3 - 2 - 3 = 1). That means every integer greater than 1 can be expressed as nonnegative combination of 2 and 3. Also 0 can be expressed (a=b=0). So indeed the only non-representable nonnegative integer is 1. So our reasoning is sound. So if k != 1 and k >=0, there exist a,b >=0 s.t. 2a+3b = k, which gives 6a+9b = 3k. So representation exists with c packages.

    Thus algorithm correct.

    Now we can implement in Python.

    Edge cases: T up to 50, input reading lines.

    We'll implement solve() reading from sys.stdin.

    We need to output exactly "True" or "False" with capital T and F as per sample.

    Now I'll produce final answer.

    But before final, let's ensure no oversight: The mapping from k to (a,b) is not necessarily unique, but we just need existence. Since we established that any nonnegative integer except 1 is representable as 2a+3b, we are done.

    But wait: Is there any constraint that a,b,c must be non-negative integers. Yes.

    So the only failure conditions: either no c exists with (U-20c)%3==0 and nonnegative, or the only c(s) give k=1.

    Now, is there any scenario where there exist multiple c but all yield k=1? That would require that for every c in the progression, (U-20c)/3 = 1. That would mean U-20c = 3 for all such c, which is impossible because U-20c changes by 20*3=60 when c increases by 3. So at most one c can give k=1. So if there is any c that yields k !=1 and k>=0, then true. Our method of checking the smallest c yields the largest k; if that k >1, then true. If that k =1, then because it's the largest k, any other c would have smaller k (could be 0 or negative). But if k=1 and it's the only c (since next c would give negative rem), then false. But if k=1 and there is another c with nonnegative rem, could that happen? Suppose smallest c yields k=1, so U-20c_min=3 => U=20c_min+3. Next c = c_min+3 gives U-20(c_min+3) = 3-60 = -57 negative, so not allowed. So no other c. So false. So indeed checking smallest c suffices.

    Thus O(1) solution is valid.

    One more test: U=0? Not in constraints, but if U=0, r=0, c=0, k=0 => true. But not needed.

    Now confirm with U=6: r=0, c=0, k=2 => true.

    U=9: k=3 => true.

    U=12: k=4 => true.

    U=15: k=5 => true.

    U=18: k=6 => true.

    U=21: k=7 => true.

    U=24: k=8 => true.

    U=27: k=9 => true.

    U=30: k=10 => true.

    U=33: k=11 => true.

    U=36: k=12 => true.

    U=39: k=13 => true.

    U=42: k=14 => true.

    All good.

    Now check U=44 to 50 as above.

    So solution is final.

    Now produce the final answer.

    We'll write code:

    import sys

    def solve(): import sys data = sys.stdin.read().strip().split() if not data: return t = int(data[0]) out = [] for i in range(1, t+1): U = int(data[i]) r = U % 3 if r == 0: c = 0 elif r == 1: c = 2 else: # r == 2 c = 1 if c > U // 20: out.append("False") else: k = (U - 20*c) // 3 if k == 1: out.append("False") else: out.append("True") sys.stdout.write("\n".join(out))

    if name == "main": solve()

    But note: The input sample: first line T, then T lines each containing U. So reading all tokens works.

    Testing with sample: T=2, U=45 and 1.

    U=45: r=0, c=0, c<=45//20=2, k=15 !=1 => True.

    U=1: r=1, c=2, 2 > 1//20=0 => False. So output True and False. Matches.

    Thus final answer.

    But perhaps we need to handle large U up to 10^7, our calculations are fine.

    Now provide explanation in final response.

    But the problem might have intended to use DP or coin change, but our solution is mathematical.

    We'll output final answer accordingly.

    Now produce final ChatGPT answer with explanation and code. ```python

    import sys

    def solve() -> None: data = sys.stdin.read().strip().split() if not data: return t = int(data[0]) out = [] for i in range(1, t + 1): U = int(data[i]) r = U % 3 # smallest c that makes (U - 20c) divisible by 3 if r == 0: c = 0 elif r == 1: c = 2 else: # r == 2 c = 1

        if c > U // 20:        # no valid c at all
            out.append("False")
        else:
            k = (U - 20 * c) // 3
            # k = 0 is fine, k = 1 is the only impossible case for 2a+3b
            if k == 1:
                out.append("False")
            else:
                out.append("True")
    
    sys.stdout.write("\n".join(out))
    

    if name == "main": solve()