Kuvaus

Olet koulun ohjelmointikilpailujoukkueen johtaja Chongqingissa CCPC-kilpailussa. Vahvistaaksesi joukkuehenkeä kilpailun jälkeen haluat järjestää yhteisen illallisen. Koska budjetti kuitenkin kului loppuun hotpot-aterialle ennen kilpailua, aterian kustannukset on jaettava tasan (eli jos $k$ henkilöä osallistuu aterialle, jonka kokonaiskustannus on $W$, jokainen maksaa $\frac{W}{k}$) kaikkien osallistujien kesken.

Joukkueessa on $n$ luokkatoveria. Jokainen illalliselle osallistuva luokkatoveri tilaa täsmälleen yhden annoksen. $i$-s luokkatoveri tilaa annoksen, joka maksaa $w_i$. Jokaisella luokkatoverilla on myös budjettirajoite $r_i$: jos aterian lopullinen jaettu kustannus ylittää arvon $r_i$, $i$-s luokkatoveri jää hotellille ja tilaa sen sijaan noutoruokaa.

Johtajana haluat maksimoida illalliselle osallistuvien luokkatovereiden määrän. Tavoitteenasi on valita $m$ luokkatoverin osajoukko siten, että jos he kukin tilaavat omat annoksensa, jaettu kustannus (heidän $m$ annoksensa hintojen summa jaettuna $m$:llä) ei ylitä kenenkään valitun $m$ luokkatoverin budjettia $r_i$. Etsi suurin mahdollinen arvo luvulle $m$.

Jos tällaista osajoukkoa ei ole olemassa millään $m \ge 1$, tulosta $0$.

Syöte

Yhdessä syötetiedostossa on useita testitapauksia. Syötteen ensimmäinen rivi sisältää yhden kokonaisluvun $T$ ($1 \le T \le 10^5$), joka ilmaisee testitapausten lukumäärän.

Jokaisessa testitapauksessa:

• Syötteen ensimmäinen rivi sisältää yhden kokonaisluvun $n$ ($1 \le n \le 10^5$), joka esittää luokkatovereiden lukumäärää.
• Seuraavaksi syötteessä on rivi, jolla on $n$ kokonaislukua, missä $i$-s kokonaisluku $w_i$ ($1 \le w_i \le 10^9$) esittää $i$-nnen luokkatoverin tilaaman annoksen hintaa.
• Sen jälkeen syötteessä on rivi, jolla on $n$ kokonaislukua, missä $i$-s kokonaisluku $r_i$ ($1 \le r_i \le 10^9$) esittää enimmäishintaa, jonka $i$-s luokkatoveri on valmis maksamaan.

On taattu, että lukujen $n$ summa yli kaikkien testitapausten ei ylitä arvoa $10^5$.

Tuloste

Tulosta jokaista testitapausta kohden rivi, jolla on yksi kokonaisluku: tehtävän vastaus.

Esimerkki

Esimerkkisyöte 1

2
5
1 2 3 4 5
5 4 3 2 1
10
3 1 4 1 5 9 2 6 5 3
5 8 9 7 9 3 2 3 8 4

Esimerkkituloste 1

3
7