Masala #0175

Shermat robotni \(OX\) o'qi bo'yicha harakatlantiradigan dastur tuzdi va qanchadir vaqt o’tgach robot harakatlangan nuqtalarning koordinatalarini ekranga chiqardi. Lekin Shermat har doimgidek nimanidir esdan chiqargandi. Bu safar u probellarni esdan chiqaribdi. Endi robot jami \(k\) ta nuqtaga borgani va robot borgan ixtiyoriy ikkita qo'shni nuqtalar orasidagi masofa \([l,r]\) oraliqda bo’lishini (har bir \(i \space (1 ≤ i < k)\) uchun \(l ≤ |x_i - x_i+1| ≤ r\)) hisobga olib, sizdan hozirgi ma’lumotlarni necha xil usulda tiklash mumkinligini so'ramoqda.

Yodda tuting. Nuqtani koordinatasi nomanfiy butun son bo'lib, oldida nollar bo'lmasligi lozim (0 sonini o'zidan tashqari).

Birinchi qatorda bitta butun \(t\) soni - testlar soni beriladi \((1 ≤ t ≤ 100)\). Keyingi \(t\) ta qatorda Shermat ekranga chiqargan nuqtalarni bildiruvchi \(x\) soni, shuningdek, \(l\), \(r\), va \(k\) sonlari beriladi. \((1 ≤ x ≤ 10^{18}, 0 ≤ l, r ≤ 10^{18}, 1 ≤ k ≤ 18)\).

Har bir test uchun javobni alohida qatorda chiqaring.