Alien dari luar angkasa (akhirnya!) telah menyerbu Bumi. Lindungi dirimu, atau kamu akan dihancurkan menjadi partikel! Atau diasimilasi. Atau dimakan. Kami belum yakin.

Alien mengikuti pola serangan yang diketahui. Ada $n$ penyerang, dan penyerang ke-$i$ muncul pada waktu $a_i$, berjarak $d_i$ darimu. Ia harus dihancurkan selambat-lambatnya pada waktu $b_i$, atau ia akan menembakkan senjatanya, yang pasti akan mengakhiri pertarungan.

Senjatamu adalah meriam area, yang dapat diatur ke kekuatan apa pun. Jika ditembakkan dengan kekuatan $R$, senjata ini seketika menghancurkan semua alien pada jarak paling jauh $R$. Senjata ini juga menghabiskan $R$ sel bahan bakar.

Tentukan biaya minimum (diukur dalam sel bahan bakar) untuk menghancurkan semua alien tanpa terbunuh.

Ukuran berkas masukan tidak melebihi 0.1 MiB.

Masukan

Baris pertama masukan berisi jumlah kasus uji $T$. Deskripsi kasus-kasus uji menyusul:

Setiap kasus dimulai dengan satu baris berisi jumlah alien $n$ ($1 \le n \le 300$). Dari $n$ baris berikutnya, baris ke-$i$ berisi tiga bilangan bulat $a_i$, $b_i$, $d_i$ ($1 \le a_i < b_i \le 10\,000$; $1 \le d_i \le 10\,000$). Alien ke-$i$ muncul pada waktu $a_i$, tidak bertindak hingga $b_i$, dan berjarak $d_i$ darimu.

Keluaran

Untuk setiap kasus uji, keluarkan satu baris berisi jumlah sel minimum yang diperlukan untuk menghancurkan semua alien.

Contoh

Masukan 1

1
3
1 4 4
4 7 5
3 4 7

Keluaran 1

7