結果
| 問題 | No.1409 Simple Math in yukicoder |
| ユーザー |
 FF256grhy
|
| 提出日時 | 2023-08-24 19:44:10 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 565 ms / 2,000 ms |
| コード長 | 32,687 bytes |
| コンパイル時間 | 10,448 ms |
| コンパイル使用メモリ | 297,428 KB |
| 実行使用メモリ | 5,376 KB |
| 最終ジャッジ日時 | 2024-06-02 09:13:56 |
| 合計ジャッジ時間 | 53,784 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 3 ms
5,248 KB |
| testcase_01 | AC | 2 ms
5,248 KB |
| testcase_02 | AC | 2 ms
5,376 KB |
| testcase_03 | AC | 2 ms
5,376 KB |
| testcase_04 | AC | 2 ms
5,376 KB |
| testcase_05 | AC | 2 ms
5,376 KB |
| testcase_06 | AC | 2 ms
5,376 KB |
| testcase_07 | AC | 77 ms
5,376 KB |
| testcase_08 | AC | 278 ms
5,376 KB |
| testcase_09 | AC | 67 ms
5,376 KB |
| testcase_10 | AC | 227 ms
5,376 KB |
| testcase_11 | AC | 263 ms
5,376 KB |
| testcase_12 | AC | 222 ms
5,376 KB |
| testcase_13 | AC | 90 ms
5,376 KB |
| testcase_14 | AC | 63 ms
5,376 KB |
| testcase_15 | AC | 93 ms
5,376 KB |
| testcase_16 | AC | 102 ms
5,376 KB |
| testcase_17 | AC | 365 ms
5,376 KB |
| testcase_18 | AC | 154 ms
5,376 KB |
| testcase_19 | AC | 200 ms
5,376 KB |
| testcase_20 | AC | 148 ms
5,376 KB |
| testcase_21 | AC | 122 ms
5,376 KB |
| testcase_22 | AC | 235 ms
5,376 KB |
| testcase_23 | AC | 49 ms
5,376 KB |
| testcase_24 | AC | 36 ms
5,376 KB |
| testcase_25 | AC | 228 ms
5,376 KB |
| testcase_26 | AC | 238 ms
5,376 KB |
| testcase_27 | AC | 423 ms
5,376 KB |
| testcase_28 | AC | 399 ms
5,376 KB |
| testcase_29 | AC | 404 ms
5,376 KB |
| testcase_30 | AC | 403 ms
5,376 KB |
| testcase_31 | AC | 409 ms
5,376 KB |
| testcase_32 | AC | 387 ms
5,376 KB |
| testcase_33 | AC | 418 ms
5,376 KB |
| testcase_34 | AC | 395 ms
5,376 KB |
| testcase_35 | AC | 414 ms
5,376 KB |
| testcase_36 | AC | 410 ms
5,376 KB |
| testcase_37 | AC | 506 ms
5,376 KB |
| testcase_38 | AC | 534 ms
5,376 KB |
| testcase_39 | AC | 565 ms
5,376 KB |
| testcase_40 | AC | 497 ms
5,376 KB |
| testcase_41 | AC | 478 ms
5,376 KB |
| testcase_42 | AC | 490 ms
5,376 KB |
| testcase_43 | AC | 492 ms
5,376 KB |
| testcase_44 | AC | 516 ms
5,376 KB |
| testcase_45 | AC | 487 ms
5,376 KB |
| testcase_46 | AC | 511 ms
5,376 KB |
| testcase_47 | AC | 534 ms
5,376 KB |
| testcase_48 | AC | 504 ms
5,376 KB |
| testcase_49 | AC | 499 ms
5,376 KB |
| testcase_50 | AC | 491 ms
5,376 KB |
| testcase_51 | AC | 431 ms
5,376 KB |
| testcase_52 | AC | 521 ms
5,376 KB |
| testcase_53 | AC | 506 ms
5,376 KB |
| testcase_54 | AC | 498 ms
5,376 KB |
| testcase_55 | AC | 507 ms
5,376 KB |
| testcase_56 | AC | 517 ms
5,376 KB |
| testcase_57 | AC | 482 ms
5,376 KB |
| testcase_58 | AC | 513 ms
5,376 KB |
| testcase_59 | AC | 503 ms
5,376 KB |
ソースコード
#include <bits/stdc++.h>
using namespace std;
#define incII(i, l, r) for(decay_t<decltype(r)> i = (l) ; i <= (r); i++)
#define incIX(i, l, r) for(decay_t<decltype(r)> i = (l) ; i < (r); i++)
#define incXI(i, l, r) for(decay_t<decltype(r)> i = (l) + 1; i <= (r); i++)
#define incXX(i, l, r) for(decay_t<decltype(r)> i = (l) + 1; i < (r); i++)
#define decII(i, l, r) for(decay_t<decltype(r)> i = (r) ; i >= (l); i--)
#define decIX(i, l, r) for(decay_t<decltype(r)> i = (r) - 1; i >= (l); i--)
#define decXI(i, l, r) for(decay_t<decltype(r)> i = (r) ; i > (l); i--)
#define decXX(i, l, r) for(decay_t<decltype(r)> i = (r) - 1; i > (l); i--)
#define inc(i, n) incIX(i, 0, n)
#define dec(i, n) decIX(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define dec1(i, n) decII(i, 1, n)
auto inII = [](auto a, auto l, auto r) -> bool { return (l <= a && a <= r); };
auto inIX = [](auto a, auto l, auto r) -> bool { return (l <= a && a < r); };
auto inXI = [](auto a, auto l, auto r) -> bool { return (l < a && a <= r); };
auto inXX = [](auto a, auto l, auto r) -> bool { return (l < a && a < r); };
auto setmin = [](auto & a, auto b) -> bool { return (b < a ? a = b, true : false); };
auto setmax = [](auto & a, auto b) -> bool { return (b > a ? a = b, true : false); };
auto setmineq = [](auto & a, auto b) -> bool { return (b <= a ? a = b, true : false); };
auto setmaxeq = [](auto & a, auto b) -> bool { return (b >= a ? a = b, true : false); };
using LL = long long int;
using LD = long double;
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define MT make_tuple
#define FI first
#define SE second
#define FR front()
#define BA back()
#define ALL(a) begin(a), end(a)
#define RALL(a) rbegin(a), rend(a)
#define RV(a) reverse(ALL(a))
#define ST(a) sort(ALL(a))
#define RST(a) sort(RALL(a))
#define SC static_cast
#define SI(a) SC<int>(a.size())
#define SL(a) SC<LL>(a.size())
#define RF(e, ...) for(auto && e: __VA_ARGS__)
#define SF(a, ...) for(auto && [__VA_ARGS__]: a)
#define until(...) while(not(__VA_ARGS__))
#define if_not(...) if(not(__VA_ARGS__))
#define ef else if
#define UR assert(false)
template<typename A> istream & operator>>(istream & is, vector<A> & v);
template<typename A> ostream & operator<<(ostream & os, vector<A> const & v);
template<typename A, size_t N> istream & operator>>(istream & is, array<A, N> & a);
template<typename A, size_t N> ostream & operator<<(ostream & os, array<A, N> const & a);
template<typename A, typename B> istream & operator>>(istream & is, pair<A, B> & p);
template<typename A, typename B> ostream & operator<<(ostream & os, pair<A, B> const & p);
template<typename ... A> istream & operator>>(istream & is, tuple<A ...> & t);
template<typename ... A> ostream & operator<<(ostream & os, tuple<A ...> const & t);
template<int I = 0, typename T> void tin_ (istream & is, T & t) { if constexpr(I < tuple_size<T>::value) { is >> get<I>(t); tin_<I + 1>(is, t); } }
template<int I = 0, typename T> void tout_(ostream & os, T const & t) { if constexpr(I < tuple_size<T>::value) { if(I != 0) { os << " "; } os << get<I>(t); tout_<I + 1>(os, t); } }
template<typename A> istream & operator>>(istream & is, vector<A> & v) { for(auto && e: v) { is >> e; } return is; }
template<typename A> ostream & operator<<(ostream & os, vector<A> const & v) { string ss; for(auto && e: v) { os << ss << e; ss = " "; } return os; }
template<typename A, size_t N> istream & operator>>(istream & is, array<A, N> & a) { for(auto && e: a) { is >> e; } return is; }
template<typename A, size_t N> ostream & operator<<(ostream & os, array<A, N> const & a) { string ss; for(auto && e: a) { os << ss << e; ss = " "; } return os; }
template<typename A, typename B> istream & operator>>(istream & is, pair<A, B> & p) { return is >> p.first >> p.second; }
template<typename A, typename B> ostream & operator<<(ostream & os, pair<A, B> const & p) { return os << p.first << " " << p.second; }
template<typename ... A> istream & operator>>(istream & is, tuple<A ...> & t) { tin_ (is, t); return is; }
template<typename ... A> ostream & operator<<(ostream & os, tuple<A ...> const & t) { tout_(os, t); return os; }
auto * IS = & cin;
auto * OS = & cout;
template<typename ... A> void in(A & ... a) { (* IS >> ... >> a); }
#define IN(...) __VA_ARGS__; in(__VA_ARGS__)
template<typename A > auto make_v(A a) { return a; }
template<typename A, typename ... M> auto make_v(A a, int n, M ... m) { return vector(n, make_v(a, m ...)); }
template<typename A, typename ... N> auto read_v(N ... n) { auto a = make_v(A { }, n ...); in(a); return a; }
void out_([[maybe_unused]] string const & s) { }
template<typename A > void out_([[maybe_unused]] string const & s, A const & a) { * OS << a; }
template<typename A, typename ... B> void out_( string const & s, A const & a, B const & ... b) { * OS << a << s; out_(s, b ...); }
auto outF = [](string const & s, string const & t, auto const & ... a) { out_(s, a ...); * OS << t << flush; };
auto outN = [](auto const & ... a) { outF("" , "" , a ...); };
auto outS = [](auto const & ... a) { outF(" " , " " , a ...); };
auto outL = [](auto const & ... a) { outF("\n", "\n", a ...); };
auto outSN = [](auto const & ... a) { outF(" " , "" , a ...); };
auto outNL = [](auto const & ... a) { outF("" , "\n", a ...); };
auto outSL = [](auto const & ... a) { outF(" " , "\n", a ...); };
auto out = outSL;
template<typename A > void disp_(A const & a) { * OS << a; }
template<typename A, typename ... T> void disp_(A const & a, string const & s, T const & ... t) { string ss; for(auto && e: a) { * OS << ss; ss = s; disp_(e, t ...); } }
auto dispI = [](auto const & a, auto const & s, auto const & ... t) { disp_(a, t ...); * OS << s << flush; };
auto dispT = [](auto const & a, auto const & s, auto const & ... t) { for(auto && e: a) { disp_(e, t ...); * OS << s; } * OS << flush; };
auto dispL = [](auto const & a, auto const & ... t) { dispT(a, "\n", t ...); };
struct OS_init { OS_init() { * OS << boolalpha << fixed << setprecision(20); } } os_init_;
// ---- ----
map<LL, LL> mp = { {95471,43},{88079,31},{97919,23},{88919,23},{87911,29},{98999,19},{63839,29},{87359,19},{88321,34},{65831,31},{93481,35},{61151,31},{92761,26},{97441,37},{83639,19},{90191,17},{75479,19},{99961,31},{87071,17},{99289,26},{99823,21},{72959,17},{94079,13},{93719,13},{66071,22},{92399,13},{89231,14},{70199,17},{87481,29},{92569,31},{89759,13},{71711,17},{61031,22},{82183,21},{98711,13},{57791,26},{75431,19},{66239,17},{38639,29},{64609,35},{95929,26},{89209,22},{84719,13},{64679,17},{99839,11},{67679,19},{53231,23},{50951,23},{99119,11},{57119,19},{89041,29},{82799,13},{96479,11},{62039,17},{84551,19},{90121,23},{84503,15},{94559,11},{79631,13},{99431,13},{61871,19},{93239,11},{78839,13},{92951,11},{88609,17},{89591,13},{93937,15},{91199,11},{76919,13},{92401,34},{90599,11},{91249,17},{56591,19},{90359,11},{58439,17},{64151,17},{35279,29},{78311,14},{97609,17},{96431,11},{75239,13},{64279,29},{92111,13},{95479,17},{86399,11},{51239,23},{73079,13},{90289,23},{80471,17},{88729,17},{97151,13},{83471,11},{85201,22},{63311,17},{53759,17},{86351,13},{91393,23},{89519,11},{67271,14},{97777,17},{73751,13},{68879,13},{81359,11},{79151,13},{81119,11},{77711,14},{77591,13},{85369,17},{70729,22},{66359,13},{77999,11},{77167,21},{80809,19},{77279,11},{63361,37},{74159,13},{70439,13},{73679,14},{72431,13},{76831,29},{76079,11},{82031,11},{64319,13},{68351,17},{93889,14},{85751,14},{63719,13},{53089,31},{96911,11},{74759,11},{71761,44},{65951,13},{31391,31},{76991,13},{72551,13},{87671,11},{78191,11},{95191,13},{50111,17},{93911,11},{74929,17},{80279,11},{91381,17},{78241,19},{72719,11},{61681,29},{70249,23},{46679,17},{93601,22},{69119,13},{87049,19},{66301,22},{71399,11},{46199,17},{77951,11},{59351,13},{49871,17},{86929,14},{94009,13},{95881,13},{73609,19},{51361,37},{95231,11},{99191,11},{69191,11},{95111,11},{58511,13},{80929,19},{68711,11},{92809,14},{80039,11},{77899,14},{48889,34},{90841,17},{83431,12},{56999,13},{76579,14},{90217,22},{87649,17},{89653,17},{42719,19},{94033,15},{87541,18},{40031,19},{66191,11},{90439,13},{65519,11},{55439,13},{71879,11},{71039,11},{70271,11},{55079,13},{67369,19},{70009,19},{56611,26},{93001,14},{79609,14},{43801,31},{74209,19},{46489,29},{97849,13},{89431,11},{59929,19},{82039,15},{99719,7},{82021,22},{80209,14},{69431,13},{90019,14},{94561,14},{98639,7},{98519,7},{62639,11},{67489,23},{77351,14},{85297,15},{97871,7},{83689,13},{98911,12},{76129,17},{96959,7},{78791,11},{95089,13},{96671,7},{86689,13},{98641,17},{88591,15},{51719,13},{94777,10},{89449,11},{55441,38},{98929,11},{95279,7},{71671,15},{94439,7},{36599,19},{93967,11},{95569,14},{93479,7},{59471,11},{53591,13},{67751,13},{34319,19},{87697,17},{92639,7},{84199,11},{58679,11},{98809,17},{96769,22},{91711,11},{58631,19},{53881,31},{88471,11},{75577,17},{43991,17},{59879,14},{58271,11},{49199,13},{74231,11},{91079,7},{67511,11},{60889,21},{34919,19},{43391,17},{74471,11},{90239,7},{68041,22},{98953,10},{61631,11},{62401,17},{84239,11},{83311,12},{89399,7},{76943,10},{80111,11},{84121,13},{91513,10},{51769,19},{81761,12},{89329,13},{99551,7},{67079,11},{87719,7},{94531,10},{87119,7},{79801,23},{58391,11},{86711,7},{91367,11},{56519,13},{91081,17},{74311,12},{86287,11},{27191,26},{91009,11},{69403,14},{85991,11},{70849,17},{89521,14},{97511,7},{85531,14},{85439,7},{81331,12},{85199,7},{74071,14},{80329,11},{88513,10},{99349,11},{93241,13},{44351,19},{89659,10},{92623,11},{77569,13},{66169,14},{81769,11},{84649,13},{83591,7},{73681,14},{83399,7},{57839,11},{83761,11},{53569,19},{83231,7},{52919,11},{77137,13},{91753,10},{91961,15},{96469,10},{44519,13},{82559,7},{94993,10},{55511,11},{76801,17},{99251,10},{92831,7},{78079,12},{81839,7},{81671,7},{87931,10},{97171,10},{81239,7},{86209,11},{61441,17},{51551,11},{80831,7},{91151,7},{99679,6},{90911,7},{80231,7},{77761,11},{36791,17},{90001,13},{61991,13},{79559,7},{68881,22},{94201,11},{88897,11},{98017,7},{79319,7},{97879,6},{36721,37},{95239,7},{94771,10},{49921,23},{95857,10},{99709,10},{53173,18},{78479,7},{96799,6},{96697,7},{91309,10},{77689,14},{63671,11},{99529,7},{56809,17},{49559,11},{41879,13},{99241,11},{63691,15},{64969,13},{79691,10},{69001,19},{90073,10},{33479,17},{91801,13},{47041,29},{76679,7},{64849,13},{93529,11},{87959,7},{83497,10},{52321,17},{94057,7},{76031,7},{56951,13},{84697,11},{66889,17},{74551,11},{91969,13},{70489,17},{92479,6},{74761,19},{73369,11},{88873,15},{67843,14},{74279,7},{87961,14},{91159,6},{46919,11},{66361,17},{59341,14},{76441,11},{50231,11},{88771,11},{46511,11},{39841,31},{40751,14},{60331,12},{47881,29},{81853,11},{55921,21},{71999,7},{68821,14},{94207,6},{47351,13},{81551,7},{49009,19},{41161,22},{81421,11},{94441,11},{99767,5},{93487,6},{99623,5},{94151,7},{45191,11},{70999,11},{70919,7},{71011,15},{97231,6},{85009,13},{86161,14},{98927,5},{26591,22},{77641,13},{98807,5},{88129,11},{98663,5},{69151,11},{73561,13},{98543,5},{90481,14},{98327,5},{68329,11},{86719,6},{35591,17},{98207,5},{93997,11},{70079,7},{79031,7},{97967,5},{97943,5},{69959,7},{99881,6},{69911,7},{97847,5},{74521,13},{97607,5},{97583,5},{81071,7},{92551,7},{97463,5},{97367,5},{59053,15},{44159,11},{97127,5},{97103,5},{82609,11},{85621,10},{97007,5},{90823,6},{68161,13},{96527,5},{79153,10},{86111,11},{96289,11},{54601,22},{96263,5},{96167,5},{68639,7},{99409,11},{76873,10},{93169,11},{90007,6},{64231,12},{60457,13},{94951,6},{56401,13},{95783,5},{68399,7},{40609,22},{95327,5},{76871,7},{72911,11},{59497,15},{79633,13},{97711,11},{95087,5},{55849,14},{94847,5},{94823,5},{50857,19},{94727,5},{67631,7},{94583,5},{43201,23},{91631,7},{94463,5},{50587,14},{46751,11},{94343,5},{88423,6},{42839,11},{39373,22},{78781,10},{94007,5},{76511,7},{98473,10},{83077,14},{86951,7},{93887,5},{66959,7},{35999,13},{85081,7},{66791,7},{93503,5},{43271,13},{54311,11},{93407,5},{93383,5},{93287,5},{93263,5},{93199,7},{89119,6},{93047,5},{83341,10},{92959,6},{92927,5},{70201,14},{92567,5},{99013,6},{41999,11},{79201,13},{76631,7},{91967,5},{91943,5},{93761,6},{81031,6},{91823,5},{98317,6},{80953,7},{66529,19},{98257,10},{91703,5},{81649,11},{91583,5},{91463,5},{87721,11},{99131,6},{84431,7},{91141,6},{54049,11},{75793,10},{84191,7},{74713,10},{90887,5},{64871,7},{77929,14},{90647,5},{90527,5},{90407,5},{96823,5},{36241,19},{90263,5},{72671,7},{83071,14},{90023,5},{88799,7},{84223,6},{96223,5},{89783,5},{28031,19},{89689,7},{33289,29},{98041,13},{79039,6},{89567,5},{82129,13},{47591,11},{95773,7},{76039,12},{66721,13},{89303,5},{81049,7},{77521,7},{78649,11},{89087,5},{70327,11},{33049,29},{63599,7},{78889,11},{99391,6},{41521,22},{38231,13},{88607,5},{41809,21},{88463,5},{94687,5},{53639,11},{88223,5},{77719,6},{43151,11},{88007,5},{77551,6},{87887,5},{51071,11},{87767,5},{87743,5},{87739,7},{65731,10},{87623,5},{97729,13},{39791,11},{77191,6},{83719,6},{43319,11},{87407,5},{87383,5},{62351,7},{92377,7},{72649,7},{96589,6},{93103,5},{70429,10},{86783,5},{81343,6},{86353,10},{94261,6},{76471,6},{52391,11},{70141,10},{52201,17},{86423,5},{58237,15},{92503,5},{80191,11},{86183,5},{61559,7},{92317,6},{39119,11},{88969,7},{90931,11},{67819,10},{99109,6},{84481,7},{85847,5},{95131,7},{91957,7},{95257,5},{85711,6},{85703,5},{85607,5},{85487,5},{52081,17},{96419,6},{90529,7},{85247,5},{85223,5},{30911,17},{91237,6},{85103,5},{60719,7},{65521,17},{47431,12},{81199,6},{90847,5},{89113,7},{58111,12},{90583,5},{68111,7},{97429,6},{76561,17},{78901,10},{84319,6},{84263,5},{90247,5},{69239,7},{84143,5},{92269,10},{84047,5},{69073,10},{59999,7},{71569,19},{93229,6},{83903,5},{68279,7},{49391,11},{73999,6},{83663,5},{18191,29},{53161,14},{83423,5},{45863,10},{87991,6},{83207,5},{37799,11},{79873,7},{48409,17},{83063,5},{77713,7},{88807,5},{82847,5},{98621,7},{82727,5},{41039,11},{68491,10},{82487,5},{99527,5},{82463,5},{72679,6},{76231,6},{89809,7},{82279,6},{60937,10},{82223,5},{33601,29},{93787,7},{91297,5},{15791,29},{98143,5},{96331,10},{82007,5},{60649,11},{78031,7},{69829,10},{81647,5},{44641,19},{75289,13},{81527,5},{75721,11},{64081,11},{58199,7},{58151,7},{82729,7},{99991,6},{87133,6},{58031,7},{97841,6},{69847,10},{81047,5},{81023,5},{47711,11},{71359,6},{57719,7},{80783,5},{80687,5},{80567,5},{99721,11},{61153,10},{69709,11},{80447,5},{56929,14},{52369,13},{87221,10},{80207,5},{80149,6},{98491,7},{79967,5},{74831,7},{97501,7},{39191,11},{79943,5},{79847,5},{86771,6},{79823,5},{64919,7},{84961,11},{64271,7},{23399,17},{96661,7},{83641,7},{56711,7},{79367,5},{97081,7},{51631,15},{79111,6},{79103,5},{35951,11},{71881,7},{46103,10},{98689,7},{65111,7},{78887,5},{76099,7},{55903,11},{83221,7},{68473,10},{35759,11},{48049,17},{84247,5},{78623,5},{47569,17},{69313,10},{56039,7},{82009,13},{78439,6},{80761,11},{55249,11},{65617,13},{70381,10},{93097,10},{62971,10},{89839,7},{81559,6},{79669,10},{52631,13},{55631,7},{86509,6},{83407,5},{66553,10},{77783,5},{95063,5},{97213,5},{77687,5},{62591,7},{77543,5},{66463,10},{77447,5},{96757,5},{35159,11},{84011,6},{62017,10},{76819,7},{54959,7},{72103,6},{76847,5},{98011,10},{80737,7},{70991,7},{81409,7},{92863,6},{76607,5},{60887,7},{76487,5},{76463,5},{29399,13},{76367,5},{96601,11},{76343,5},{61511,7},{95317,5},{65809,11},{91453,6},{76103,5},{51169,14},{75983,5},{82571,6},{92581,6},{95401,7},{71143,6},{59951,11},{66919,6},{81223,5},{75767,5},{34439,11},{75743,5},{84751,6},{75679,6},{67531,10},{63913,13},{92641,11},{65713,10},{75527,5},{89891,7},{91127,5},{92791,6},{94309,6},{83701,6},{59809,17},{75937,10},{92431,6},{49003,13},{91369,7},{92311,7},{82013,11},{92177,6},{61609,13},{52009,17},{56197,13},{87121,7},{93637,5},{72931,10},{74903,5},{65449,11},{77617,10},{85021,7},{71209,7},{68771,10},{74687,5},{48481,17},{33911,11},{53279,7},{74567,5},{37321,23},{35111,13},{52711,23},{55057,10},{69463,6},{57241,11},{92051,6},{73943,5},{33599,11},{73847,5},{73823,5},{90401,6},{22751,21},{73727,5},{66949,10},{73607,5},{88001,6},{58099,10},{73583,5},{64879,6},{95869,6},{58367,7},{30071,13},{33311,11},{60169,11},{58991,7},{78367,5},{73127,5},{42187,13},{85303,5},{35831,11},{52189,13},{78277,6},{59209,11},{95233,5},{84761,7},{94321,7},{59671,12},{72767,5},{90863,5},{82139,6},{84631,6},{77863,5},{80713,5},{90793,5},{72623,5},{51839,7},{90709,6},{72503,5},{91921,13},{85619,6},{71233,11},{72383,5},{96457,5},{63799,6},{72287,5},{51599,7},{72169,7},{72167,5},{59159,7},{72047,5},{51431,7},{93913,5},{59399,7},{75991,11},{95737,5},{79777,5},{85381,6},{71089,11},{71663,5},{60611,10},{71443,11},{79357,7},{41281,17},{71327,5},{87691,7},{98407,6},{44491,13},{84061,7},{96763,5},{70951,6},{88681,7},{78121,11},{54193,10},{80233,7},{78643,11},{70823,5},{98737,5},{96001,7},{67391,7},{67273,7},{94153,5},{70607,5},{70583,5},{75583,5},{57047,7},{37511,11},{58129,13},{98377,5},{70487,5},{28871,13},{71023,6},{78691,7},{57191,7},{85429,6},{54973,14},{70223,5},{73849,7},{88801,7},{66571,7},{99793,5},{38281,14},{55291,11},{96097,5},{95467,5},{93337,5},{49991,7},{49919,7},{26879,13},{87337,5},{69859,10},{69767,5},{95107,5},{92857,5},{69623,5},{97259,6},{74383,5},{69383,5},{94603,5},{36671,13},{69263,5},{74167,5},{51907,11},{74143,5},{84463,5},{67559,7},{69143,5},{41467,14},{37489,19},{33871,15},{97003,7},{79579,10},{83401,7},{67759,6},{76597,7},{68903,5},{70241,6},{85091,6},{38239,13},{38569,14},{68687,5},{82499,6},{56299,10},{73477,6},{68567,5},{68543,5},{49537,10},{90071,7},{68447,5},{73303,5},{72481,11},{31079,11},{75913,5},{77041,7},{71479,6},{70111,6},{42649,11},{68207,5},{45127,12},{74051,6},{68087,5},{68071,6},{23209,31},{82561,7},{67967,5},{67943,5},{53611,10},{72727,7},{48479,7},{62921,14},{32831,13},{67741,6},{92347,5},{75193,7},{48311,7},{81157,6},{71161,11},{44449,13},{72161,6},{48239,7},{81013,6},{33071,11},{55799,7},{80917,6},{67343,5},{81967,5},{81041,6},{67247,5},{82591,6},{47951,7},{91243,5},{53951,7},{66863,5},{59779,10},{83449,13},{98081,6},{47639,7},{49031,13},{90907,5},{86011,7},{91121,6},{73897,5},{94873,5},{66383,5},{99181,7},{34303,17},{94693,5},{30119,11},{70969,11},{93133,6},{52249,13},{66047,5},{58231,6},{35281,23},{47111,7},{65927,5},{88747,7},{70627,7},{49801,13},{61687,6},{29879,11},{65687,5},{95747,5},{51817,10},{97561,11},{27431,17},{65543,5},{87313,5},{70921,13},{74449,13},{65479,7},{65447,5},{48121,13},{49081,11},{65423,5},{42841,23},{98047,5},{65327,5},{39199,17},{68521,7},{72337,7},{73417,10},{65183,5},{46559,7},{72421,6},{54121,13},{52511,7},{83089,7},{99023,5},{65063,5},{39769,13},{54721,11},{71471,7},{67129,7},{72073,5},{78401,13},{92593,5},{70451,6},{81001,11},{64439,7},{43399,13},{48673,15},{26759,13},{69127,5},{86017,5},{45959,7},{64223,5},{71329,7},{93563,5},{67219,11},{56479,6},{64007,5},{62311,6},{49831,12},{63863,5},{51481,17},{45599,7},{83257,5},{30671,11},{47521,17},{71389,11},{90997,5},{79537,7},{57829,10},{51577,10},{36217,19},{58831,11},{63527,5},{69011,6},{49033,10},{78167,5},{43963,12},{58711,6},{90313,5},{30431,11},{55009,7},{51479,7},{86137,5},{96493,5},{29231,13},{94597,5},{24239,13},{62927,5},{62903,5},{61751,7},{44879,7},{28559,11},{79481,6},{61729,7},{51691,10},{28729,22},{82189,10},{62687,5},{58687,6},{54409,7},{75503,5},{89293,5},{82231,7},{78721,7},{62423,5},{92899,7},{53731,12},{69337,5},{64663,6},{70379,6},{62327,5},{62303,5},{60289,7},{91153,7},{69193,10},{77797,5},{56569,11},{51853,11},{62207,5},{81097,5},{28081,19},{41851,15},{44279,7},{61967,5},{64891,10},{66343,5},{79561,7},{45361,11},{95603,5},{93983,5},{51241,17},{61703,5},{87793,5},{18119,17},{74201,6},{71059,7},{61583,5},{61487,5},{61463,5},{92143,5},{76777,5},{57041,11},{54151,6},{61343,5},{45289,14},{64303,6},{76537,5},{81181,6},{65497,7},{59473,10},{66601,7},{83227,5},{73237,6},{61007,5},{21787,23},{82657,10},{41761,19},{50773,11},{85213,6},{92221,6},{65167,5},{75011,6},{60647,5},{95989,6},{60623,5},{63841,17},{89071,6},{60527,5},{82193,5},{50159,7},{88117,5},{58441,13},{60383,5},{58321,11},{99577,5},{58921,13},{76649,6},{96181,6},{52861,11},{72647,5},{71263,5},{65761,7},{60167,5},{63727,6},{52609,11},{93131,6},{31849,14},{99929,3},{99871,3},{99041,6},{99817,5},{99809,3},{66541,6},{85513,5},{99713,3},{99689,3},{79657,5},{99523,5},{99487,3},{70687,5},{31751,11},{99439,3},{59663,5},{99401,3},{99377,3},{51109,10},{59581,6},{99257,3},{28631,11},{99223,3},{72889,7},{99137,3},{99103,3},{99089,3},{99079,3},{59447,5},{81043,5},{96337,5},{59359,6},{98897,3},{98873,3},{42359,7},{72469,6},{98801,3},{74077,5},{70019,6},{63463,5},{98713,5},{82261,6},{59183,5},{54503,7},{42239,7},{86171,7},{61129,7},{98479,3},{59063,5},{81457,5},{98369,3},{58967,5},{22679,13},{58943,5},{32353,15},{98129,3},{77471,7},{86269,6},{66431,7},{42169,11},{92893,5},{72823,5},{47251,10},{87211,13},{67801,11},{97927,3},{58727,5},{71809,7},{80473,5},{68209,13},{97673,3},{97649,3},{67579,7},{62743,7},{83653,5},{83617,5},{70181,7},{73009,7},{41759,7},{97303,3},{49531,10},{97241,3},{89123,5},{97073,3},{97039,3},{96953,3},{33889,13},{64633,5},{53831,7},{41519,7},{96847,3},{49339,11},{96737,3},{91573,5},{73361,11},{89137,5},{47903,7},{96497,3},{30091,21},{96353,3},{96329,3},{96281,3},{89363,5},{96233,3},{96199,3},{91129,7},{61837,6},{77479,6},{88657,5},{96017,3},{47279,7},{95959,3},{57559,6},{95911,3},{95873,3},{57503,5},{73721,6},{65089,7},{38329,13},{95791,3},{20231,29},{57383,5},{95633,3},{71713,5},{63697,5},{68749,6},{57287,5},{42409,14},{61357,6},{69821,7},{37537,13},{95393,3},{90373,5},{95369,3},{75169,7},{95311,3},{95287,3},{57143,5},{86927,5},{85121,6},{95177,3},{53281,11},{95153,3},{95071,3},{28751,14},{25919,11},{63337,5},{94999,3},{94961,3},{28439,11},{34607,10},{43591,11},{94903,3},{94889,3},{46271,7},{56807,5},{94649,3},{56783,5},{87803,5},{56687,5},{56663,5},{91873,5},{94399,3},{94351,3},{42457,11},{94327,3},{56543,5},{75337,5},{94169,3},{25679,11},{44927,7},{63211,7},{62929,14},{94063,3},{68927,5},{74161,7},{78577,5},{56311,6},{76081,7},{93809,3},{97327,5},{56209,7},{93559,3},{60133,6},{60103,5},{56087,5},{93319,3},{55871,7},{83983,5},{46141,10},{55967,5},{93151,3},{55823,5},{44089,13},{39839,7},{92921,3},{67789,6},{76003,5},{92849,3},{59617,7},{92801,3},{70351,6},{39719,7},{92647,3},{79393,5},{59509,10},{39671,7},{80963,5},{55487,5},{84407,5},{43609,14},{42193,15},{60251,6},{92369,3},{92297,3},{61981,7},{58543,6},{92233,5},{92153,3},{61417,5},{92119,3},{60601,11},{92033,3},{58567,6},{77017,7},{89797,5},{68917,5},{55127,5},{54631,6},{55103,5},{91807,3},{48589,10},{54983,5},{67189,6},{91591,3},{91577,3},{74923,5},{39239,7},{38351,11},{87631,6},{58451,10},{91423,3},{91303,3},{54767,5},{78193,5},{91193,3},{61231,7},{45119,7},{54647,5},{50591,7},{54623,5},{87421,6},{44809,11},{74323,5},{96157,5},{58169,6},{74941,6},{83737,5},{90703,3},{90697,5},{90679,3},{37507,17},{90631,3},{90617,3},{40429,14},{81463,5},{45631,12},{54287,5},{90473,3},{24671,11},{65881,11},{47857,7},{72313,5},{94273,5},{77377,5},{90271,3},{94849,7},{90199,3},{36871,15},{90089,3},{67121,6},{90031,3},{89983,3},{89959,3},{89897,3},{53927,5},{50929,11},{63409,7},{47713,10},{47653,13},{89753,3},{73363,5},{62071,7},{93553,5},{76837,5},{95617,5},{68371,7},{53783,5},{89633,3},{89527,3},{72871,6},{89513,3},{82141,6},{89417,3},{43711,13},{76333,5},{89017,5},{21121,19},{50047,6},{35911,12},{88951,3},{29063,10},{88937,3},{88903,3},{53327,5},{65551,6},{88817,3},{53269,7},{34729,13},{56041,7},{37991,7},{85667,5},{99643,3},{79693,5},{96553,5},{63709,6},{53087,5},{25031,13},{83773,5},{26701,22},{60961,7},{81553,5},{88289,3},{52967,5},{51511,6},{46639,6},{72043,5},{76369,11},{63743,5},{70393,5},{71341,6},{98947,3},{87881,3},{52727,5},{70297,5},{45841,7},{79063,5},{78049,7},{87751,3},{70177,5},{87679,3},{52583,5},{87583,3},{98467,3},{85333,5},{87511,3},{78301,6},{74857,5},{58189,6},{84913,5},{53791,6},{87257,3},{65413,5},{62761,7},{87103,3},{87041,3},{52223,5},{86993,3},{57571,13},{86969,3},{86959,3},{62459,6},{97771,3},{52127,5},{52103,5},{24049,19},{63647,5},{86767,3},{86743,3},{86729,3},{74293,5},{86599,3},{38449,13},{97369,7},{57097,7},{40801,13},{51679,6},{63601,7},{86369,3},{81817,5},{70657,7},{76753,5},{51767,5},{86113,5},{86263,3},{86249,3},{86239,3},{96979,3},{77557,5},{42071,7},{77527,5},{36343,13},{55333,6},{67931,6},{85999,3},{50221,13},{85903,3},{54751,6},{68713,5},{85889,3},{55207,5},{77263,5},{51503,5},{85831,3},{85817,3},{85793,3},{55931,6},{95713,5},{55681,11},{51407,5},{85639,3},{51383,5},{85601,3},{40009,11},{54581,10},{51287,5},{51263,5},{81937,5},{85313,3},{56821,6},{41231,7},{92041,7},{85193,3},{85159,3},{36479,7},{51047,5},{22391,13},{30937,15},{63793,5},{85049,3},{40151,11},{84977,3},{84967,3},{55609,13},{95539,3},{84919,3},{76423,5},{23159,11},{84871,3},{95443,3},{84809,3},{48119,7},{41399,7},{84737,3},{84713,3},{44839,6},{39359,11},{73141,7},{94447,5},{68581,6},{62137,7},{84559,3},{89671,6},{66977,5},{63247,5},{18911,14},{84391,3},{84377,3},{49939,7},{35569,11},{49681,17},{50543,5},{93703,5},{84137,3},{42859,10},{75703,5},{54851,6},{84089,3},{50423,5},{70753,5},{84017,3},{70981,6},{83921,3},{83911,3},{85933,5},{88813,5},{83873,3},{46591,6},{94219,3},{35879,7},{62773,5},{26711,11},{97177,5},{14759,17},{83609,3},{82237,5},{50087,5},{83383,3},{60013,6},{93739,3},{83273,3},{41351,7},{71353,5},{48337,10},{49943,5},{78853,5},{83137,5},{71257,5},{74797,5},{53407,5},{40559,7},{60761,6},{49823,5},{43951,6},{82913,3},{82903,3},{68531,6},{49727,5},{32257,15},{82793,3},{67723,5},{57751,6},{74413,5},{24007,17},{59051,10},{63649,7},{74719,7},{12911,23},{61933,5},{22511,11},{99017,3},{82457,3},{74197,5},{49463,5},{43969,11},{52057,7},{49451,10},{82393,5},{36793,15},{98849,3},{60727,5},{82361,3},{89833,5},{75167,5},{56989,6},{49367,5},{29599,13},{82207,3},{18959,13},{49223,5},{92227,3},{92179,3},{98321,3},{81919,3},{98297,3},{87553,5},{49103,5},{81799,3},{35059,10},{38861,14},{59207,5},{81737,3},{98057,3},{81703,3},{77801,7},{98009,3},{38461,13},{55259,6},{81569,3},{57943,5},{70309,6},{71861,7},{81439,3},{81401,3},{81353,3},{53051,6},{88327,5},{97577,3},{86077,5},{81281,3},{48767,5},{81233,3},{67153,5},{50329,7},{48647,5},{59863,5},{23831,11},{81017,3},{97169,3},{59567,5},{10559,23},{80911,3},{80897,3},{48527,5},{80863,3},{80849,3},{97001,3},{80833,5},{53857,5},{80777,3},{42751,6},{79273,5},{41131,10},{90787,3},{77101,7},{80681,3},{48407,5},{80671,3},{80657,3},{81943,5},{48383,5},{45343,6},{63073,5},{92821,6},{90619,3},{80537,3},{80527,3},{24071,11},{80489,3},{39887,7},{58369,7},{33811,15},{68113,5},{80407,3},{80369,3},{83857,5},{90403,3},{87277,5},{68737,5},{48193,7},{80287,3},{75553,5},{56737,10},{80239,3},{35401,13},{80167,3},{48079,6},{96137,3},{80071,3},{21839,11},{79999,3},{89977,5},{47977,7},{55351,7},{89923,3},{33457,10},{80449,7},{51343,5},{95801,3},{79187,5},{69661,6},{53149,6},{55343,7},{47809,7},{58771,11},{78157,6},{70121,6},{79433,3},{44111,7},{95273,3},{79337,3},{89227,3},{53719,6},{79279,3},{41959,6},{47543,5},{79231,3},{52291,7},{79159,3},{58153,10},{47629,10},{79087,3},{67777,5},{21559,15},{94793,3},{64627,5},{78977,3},{50767,5},{78919,3},{41641,13},{78857,3},{47303,5},{45481,13},{88651,3},{47269,6},{75787,5},{51721,7},{78713,3},{47161,17},{47207,5},{72661,11},{71807,5},{78583,3},{50503,5},{88339,3},{78497,3},{78487,3},{47087,5},{21911,13},{64171,7},{51131,6},{46439,7},{40849,11},{44711,7},{57781,6},{52177,5},{70423,5},{29761,17},{58309,6},{78137,3},{65353,5},{58207,5},{66877,5},{78017,3},{78007,3},{70207,5},{77983,3},{31189,13},{93497,3},{87643,3},{46727,5},{92353,5},{77839,3},{33359,7},{27241,17},{84793,5},{93257,3},{77681,3},{60793,5},{77647,3},{93113,3},{82153,5},{93089,3},{71593,5},{77513,3},{68311,6},{22129,19},{99559,3},{77431,3},{77383,3},{74821,6},{77369,3},{77359,3},{70321,7},{87013,5},{57973,5},{99367,3},{33119,7},{92657,3},{40879,6},{42281,11},{19843,19},{77153,3},{57853,5},{53401,7},{77081,3},{77047,3},{69401,6},{55021,6},{37561,11},{32999,7},{86587,3},{76961,3},{86539,3},{98887,3},{70621,6},{32299,12},{47143,6},{44041,11},{51193,5},{75407,5},{76697,3},{92009,3},{76673,3},{57493,5},{91841,3},{27409,13},{45887,5},{59833,5},{91673,3},{19087,19},{85843,3},{76303,3},{72277,5},{76289,3},{35803,14},{45767,5},{74017,7},{66683,5},{76207,3},{76159,3},{31873,11},{51673,7},{57649,13},{55171,10},{75967,3},{35977,10},{17519,13},{85363,3},{51913,10},{45503,5},{52501,10},{62497,10},{90977,3},{25321,19},{85243,3},{72251,7},{64513,5},{75641,3},{68053,5},{97159,3},{36551,7},{46649,15},{61723,5},{48487,5},{75401,3},{75391,3},{16631,19},{75377,3},{75367,3},{56473,5},{69457,5},{75223,3},{96703,3},{61909,6},{75161,3},{75079,3},{56207,5},{96487,3},{75017,3},{90017,3},{74959,3},{39679,6},{94513,5},{84307,3},{74897,3},{99833,3},{74873,3},{93581,3},{56149,6},{84211,3},{62119,7},{76249,7},{99761,3},{96079,3},{89657,3},{80173,6},{82721,6},{89561,3},{41983,6},{99497,3},{74623,3},{45121,7},{52859,6},{89393,3},{74489,3},{44687,5},{89273,3},{74377,5},{83233,7},{61561,7},{49549,6},{95527,3},{74297,3},{89153,3},{62731,10},{44543,5},{58057,7},{74177,3},{89009,3},{50833,7},{51647,7},{98729,3},{74047,3},{67607,5},{49711,7},{95143,3},{73951,3},{88721,3},{24359,11},{48131,6},{49177,5},{67021,7},{94433,5},{44207,5},{73673,3},{58897,5},{63097,5},{46901,11},{47293,6},{88241,3},{44119,6},{82699,3},{61057,5},{67103,5},{44087,5},{88169,3},{34129,11},{41491,13},{73433,3},{79451,6},{73351,3},{97687,5},{91033,5},{73327,3},{19009,23},{43943,5},{46381,7},{66809,6},{97553,3},{95971,3},{73121,3},{31319,7},{62617,5},{73039,3},{55399,6},{43789,6},{95621,3},{65557,5},{31219,10},{44017,11},{81931,3},{93607,3},{81883,3},{51991,7},{93463,3},{43607,5},{90821,3},{12479,23},{56857,7},{67057,5},{96857,3},{58537,7},{62233,7},{84313,5},{72559,3},{81619,3},{52237,6},{81547,3},{43487,5},{33961,13},{72367,3},{61297,7},{72353,3},{65053,5},{98561,3},{45943,6},{54133,5},{92767,3},{48073,5},{72089,3},{45691,7},{94613,3},{43223,5},{72031,3},{35869,10},{54013,5},{71993,3},{71983,3},{79493,5},{86857,10},{48091,7},{71887,3},{92383,3},{71849,3},{43103,5},{37993,10},{71719,3},{80683,3},{95561,3},{71647,3},{71633,3},{74257,5},{42433,10},{95441,3},{34631,7},{71537,3},{71527,3},{91951,3},{71503,3},{53629,6},{77977,5},{42863,5},{43321,13},{53353,7},{57073,5},{68281,7},{71287,3},{42767,5},{95009,3},{46451,6},{71167,3},{82633,5},{94841,3},{71129,3},{71081,3},{95923,3},{46681,11},{58481,6},{99233,3},{88993,5},{35311,11},{19319,11},{70793,3},{79627,3},{84857,3},{42407,5},{70663,3},{69833,5},{35089,11},{67651,11},{70639,3},{24181,17},{94121,3},{30949,10},{56377,5},{70457,3},{90511,3},{45247,5},{84449,3},{64621,6},{70313,3},{48649,7},{78979,3},{70183,3},{98993,3},{43441,11},{90127,3},{59377,5},{70039,3},{42023,5},{70001,3},{69991,3},{62983,5},{83969,3},{93281,3},{41927,5},{55897,5},{87473,5},{64489,7},{69857,3},{41903,5},{75853,5},{33791,7},{78553,5},{44887,5},{89767,3},{52361,6},{69809,3},{92993,3},{69737,3},{78427,3},{89599,3},{69593,3},{18311,13},{72577,5},{45641,11},{41719,6},{83417,3},{69473,3},{55049,6},{78139,3},{69439,3},{29759,7},{27551,17},{64403,5},{62383,5},{61141,6},{41543,5},{46153,5},{20639,11},{74353,5},{86371,3},{69031,3},{93187,3},{94111,3},{57529,7},{56443,5},{88663,3},{99607,3},{75217,5},{29569,17},{54371,6},{68863,3},{96377,3},{84673,10},{68791,3},{68777,3},{82529,3},{68767,3},{77347,3},{68743,3},{60631,6},{98323,3},{92683,3},{91529,3},{41183,5},{68633,3},{54377,5},{15889,21},{91457,3},{91433,3},{97961,3},{82217,3},{45673,5},{37441,17},{76963,3},{87943,3},{82073,3},{10799,19},{95213,3},{91097,3},{81953,3},{96401,3},{68239,3},{53377,5},{49369,13},{37871,7},{95383,3},{87559,3},{40847,5},{40823,5},{84457,5},{68023,3},{42961,11},{87433,5},{92671,3},{48179,6},{67927,3},{76387,3},{87223,3},{67807,3},{87151,3},{76243,3},{62081,6},{90353,3},{54679,7},{40639,7},{90281,3},{31799,11},{40591,13},{40583,5},{32957,12},{67577,3},{67567,3},{94543,3},{40519,6},{40487,5},{67447,3},{64921,7},{69481,7},{67399,3},{89849,3},{98981,3},{40343,5},{67231,3},{39313,10},{92357,3},{67169,3},{31249,23},{61223,5},{75403,3},{86143,3},{75307,3},{95803,3},{80273,3},{40127,5},{57487,6},{89057,3},{66457,5},{40039,6},{66713,3},{87557,3},{45179,6}, };
int main() {
auto primitive_root = [](LL p) -> LL {
if(mp.count(p) == 1) { return mp[p]; }
if(p == 2) { return 1; }
incIX(i, 2, p) {
LL e = i, c = 1;
until(e == 1) { e = e * i % p; c++; }
if(c == p - 1) { return i; }
}
UR;
};
int IN(t);
inc(tt, t) {
LL IN(v, x);
LL p = x * v + 1;
LL r = primitive_root(p);
LL e = 1;
inc(vv, v) { e = e * r % p; }
vector<LL> ans(x, 1);
inc(i, x - 1) { ans[i + 1] = ans[i] * e % p; }
sort(ALL(ans));
out(ans);
}
}