Masala D

Hoshimjon uyiga $n$ ta do'stini taklif qildi. Stol atrofidagi o'rindiqlar $1,2,...,n$ tartibda raqamlangan bo'lib Hoshimjonning do'stlari o'rindiqlarga joylashib olishdi. 

Unda jami $m$ ta bir birini taniydigan jufliklar ro'yxati mavjud. Ushbu ro'yxatga kiritilmagan har qanday juftliklar bir birini tanimaydi. Siz shunday $[a,a+1,a+2,...,b](1\leq a\leq b\leq n)$ segmintlarni topingki ushbu segmintdagi barcha do'stlar bir birini tanisin, bunday segmintdagi do'stlar yaxshi do'stlar segminti hisoblanadi.

Sizning vazifangiz Hoshimjonning do'stlari joylashgan stolda jami bo'lib nechta yaxshi do'stlar segminti mavjudligini aniqlashdan iborat.

Kirish faylining dastlabki satrda testlar soni $t(1\leq t\leq 20000)$ beriladi. Kiyingi satrlarda $t$ ta test beriladi, har bir test uchun $n,m(2\leq n\leq 100000,0\leq m\leq min(2n,n(n-1)/2))$mos ravishda Hoshimjonning do'stlari soni va o'zaro bir birini taniydigan juftliklar(barcha testlar uchun $t+m_i\leq 10^6, 1\leq i\leq t$). Kiyingi $m$ ta satrda $u_i,v_i(1\leq u_i, v_i\leq n, u_i \neq v_i)$ o'zaro bir birini taniydigan juftliklar.

Chiqish faylida har bir testlar uchun javobni alohida satrlarda chop eting.