#include using namespace std; typedef long long ll; typedef pair < int , int > ii; typedef vector < int > vi; typedef vector < ll > vll; typedef vector < string > vs; typedef vector < vll > matrix; #define sz(a) int((a).size()) #define sl(a) int((a).length()) #define pb push_back #define all(c) (c).begin(),(c).end() #define rall(c) (c).rbegin(),(c).rend() #define tr(con,it) for (__typeof((con).begin()) it = con.begin(); it != con.end(); it++) #define wl(x) (cout << (x) << endl) #define w(x) (cout << (x)) #define r(x) (cin >> (x)) #define FOR(i,a,b) for (int i = (a); i < (b); i++) #define ROF(i,a,b) for (int i = (b-1); i >= (a); i--) #define PP(x) tr(x,it) cout << it->first << " " << it->second << endl #define mp(x,y) make_pair((x),(y)) #define reset(x) memset((x),0,sizeof((x))) #define D1(x) cout << #x << " = " << x << endl #define D2(x,y) cout << #x << " = " << x << " " << #y << " = " << y << endl #define D3(x,y,z) cout << #x << " = " << x << " " << #y << " = " << y << " " << #z << " = " << z << endl #define D4(x,y,z,t) cout << #x << " = " << x << " " << #y << " = " << y << " " << #z << " = " << z << " " << #t << " = " << t << endl #define D5(x,y,z,t,v) cout << #x << " = " << x << " " << #y << " = " << y << " " << #z << " = " << z << " " << #t << " = " << t << " " << #v << " = " << v << endl #define MAXN 1000010 #define MAXK 15 #define MDL 1000000007 #define EPS 1e-10 #define IO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); string to_str(const int &n){ostringstream stm; stm << n;return stm.str();} string to_str(const ll &n){ostringstream stm; stm << n;return stm.str();} template string tostring(T x, int len = 0) {stringstream ss; ss << x; string r = ss.str(); if(sz(r) < len) r = string(len - sz(r), '0') + r; return r;} template void convert(string x, T& r) {stringstream ss(x); ss >> r;} ll powmod(ll a,ll b) {ll res=1;a%=MDL;for(;b;b>>=1){if(b&1)res=res*a%MDL;a=a*a%MDL;}return res;} ll modinv(ll a) { return powmod(a, MDL-2); } ll nCkMp(ll n, ll k) { ll numerator = 1,denominator = 1;for (int i=0; i=p) res++; else break; if (res>1) { if (p-d>=m) p-=d; else p=m; } s-=p; } wl(res); cerr << "case " << (tt+1) << " " << 1.0 * (clock() - t1) / CLOCKS_PER_SEC << " ms" << endl; } int main() {IO //r(T); for(tt=0;tt